本文参考MySQL官方文档，算法书籍，部分为自己观点可能有误,如果有误请指出共同讨论

一、MySQL排序可能用到的排序算法

从MySQL官方文档和源码的接口来看MySQL使用BUFFER内部快速排序算法，外部多路归并排序算法，相应的接口函数为filesort()函数，注意filesort()是一个总的接口，内部排序实际调用save_index()下的std::stable_sort\std::sort、归并排序也包含在下面接口可能为merge_many_buff()，也就像执行计划中usingfilesort的含义，他只能代表使用了排序，但是是否使用到tempfile排序是看不出来的，但是这个可以再trace看到但是线上是不可以trace的研究是可以的，随后我会演示。
还要注意usingtemporary只是说明使用了临时表存储中间结果，这里先不讨论，只看排序。

下面简要介绍两种算法原理

1、buffer内部 快速排序算法
快速排序是交换排序类算法，是冒泡排序的升级版，其原理是采用分而治之的思想，在于每趟交换设置一个基准点，将大于这个基准点的数据放到一边，大于的放到另一边，不断的进行递归完成，对于大数据量的排序快速排序一般效率优秀，在文章的最后是一个简单的快速排序的实现，如果对算法感兴趣的可以参考一下。但是至少还能进行3种优化
--小数据优化，因为快速排序对数据量小的时候并不是最优，可以使用其他排序算法如插入排序。
--尾递归优化，减少栈的使用
--基准点优化，尽量取到数据中的中间值作为基准点，这样能够让快速排序更加优化。

2、外部磁盘多路归并排序
将内部快速排序后有序的数据文件进行不断的比较得到有序的文件，每次归并多少个文件就是归并的路数
图中每一个R当然代表的一个有序的磁盘文件
下图2路归并排序(截取数据结构C语言版)

下图5路归并排序(截取数据结构C语言版)


二、MYSQL相关参数
sort_buffer_size:
当然也就是每次排序的buffer，用作内部快速排序用，如果buffer越大当然产生的物理文件也就越少，但是这个参数是会话级别的，过分加大会造成内存不足，默认256K。注意：
On Linux, there are thresholds of 256KB and
2MB where larger values may significantly slow down memory allocation, so you should consider staying
below one of those values

read_rnd_buffer_size：
除了MRR用到，这里也用到了用于 二次排序的时候对排序好的数据按照primary key(ROW_ID)按照分块的方式再次排序，意义同样在回表取数据可以尽量顺序化

max_length_for_sort_data：
单位为字节(bytes)，如果排序返回行的字段长度综合大约这个值，使用二次排序而不是一次排序，默认1024，最小值为4，如果加大这个值可能过多的使用一次排序造成高TEMPFILE空间使用而CPU不高,为什么如此后面解释。

max_sort_length：
单位为字节(bytes)，如果排序字段的长度超过这个值，只是用这个参数设置的长度，默认1024，比如text这种字段经常会大于这个值，如果加大这个值明显会提高排序的准确性，但是也意味着更高的BUFFER使用和TEMPFILE使用

三、监控磁盘排序
Sort_merge_passes：磁盘排序归并次数，减少sort_buffer_size大小会显著减少Sort_merge_passes值，并且临时文件也会变少，第五部分证明
sys.statements_with_sorting视图

四、MYSQL二次访问排序(original method)和一次访问排序(modified method)

1、二次访问排序
--读取数据只包含排序键值和rowid(primary key)放到sort buffer
--在buffer中进行快速排序，如果buffer 满则把内存中的排序数据写入tempfile
--重复上面的过程直到内部快速排序完成，并且生成多个tmepfile文件
--进行多路归并排序源码接口在merge_many_buff()，其中定义了MERGEBUFF，MERGEBUFF2 2个宏
这个在官方文档上有出现所以提出来说明一下
/* Defines used by filesort and uniques */
#define MERGEBUFF 7
#define MERGEBUFF2 15
如果有兴趣的可以仔细看看源码..
--最后一次归并的时候，只有rowid(priamry key)到最后的文件中
--对最后的文件根据rowid(primary key)访问表数据，这样就可以得到排序好的数据
这里有一个类似MRR的优化，将数据进行分块读入read_rnd_buffer_size进行
按照rowid(primary key)排序在去访问表的数据，目的在于减少随机读取造成的影响,但是这是分块的，只能减少不能杜绝，特别是数据量特别大的情况下，因为 read_rnd_buffer_size只有默认256K.

问题在于对表数据的二次访问，一次在读取数据的时候，后一次在通过排序好的rowid(primary key)进行数据的访问，并且会出现大量随机访问。

2、一次访问排序
这个就简单了，二次访问排序是把排序键值和rowid(primary key)放到sort buffer，这个就是关于需要的数据字段全部放到sort buffer比如：
select id,name1,name2 from test order by id;

这里id,name1,name2都会存放到sort buffer中。这样排序好就好了，不需要回表取数据了，当然这样做的劣势就是更大的sort buffer占用，更大tempfile占用。所以mysql使用max_length_for_sort_data来限制默认1024，这是指id,name1,name2字段的bytes长度。
因为不需要回表，所以只要一次访问数据

3、5.7.3后一次访问排序算法的优化
使用一个叫做pack优化的方法，目的在于压缩NULL减少一次访问排序算法对sort buffer和tempfile的过多使用
原文：
without packing, a VARCHAR(255)
column value containing only 3 characters takes 255 characters in the sort buffer. With packing,
the value requires only 3 characters plus a two-byte length indicator. NULL values require only
a bitmask.
但是我在做MYSQL TRACE的时候发现这还有一个unpack的过程，并且每一行每一个字段都需要pack unpack
随后证明

关于使用了的那种排序方式在执行计划中都体现为filesort不好弄清楚，但是我们可以通过trace的方式，在官方文档也说了，但是我使用了对MYSQLD的trace方式来做