歸并排序

歸并：将兩個或兩個以上的有序表組合成一個新的有序表

初始序列看成n個有序子序列，每個子序列長度為1

兩兩合并，得到n/2個長度為2或1的有序子序列

再兩兩合并，重複直至得到一個長度為n的有序序列為止

1.為避免順序存儲時大量移動記錄的開銷，可以考慮用鍊式作為存儲結構

直接插入排序、歸并排序

2.不宜采用鍊式作為存儲結構的

折半插入排序、希爾排序、快速排序、堆排序

n較大時

（1）分布随機，穩定性不做要求，則采用快速排序

（2）記憶體允許，要求排序穩定時，則采用歸并排序

（3）可能會出現正序或逆序，穩定性不做要求，則采用堆排序或歸并排序

n較小時

（1）基本有序，要求穩定，則采用直接插入排序

（2）分布随機，穩定性不做要求，則采用直接選擇排序，若排序碼不接近逆序，也可以采用直接插入排序。