? ? 歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（分治法將問題分(divide)成一些小的問題然后遞歸求解华坦，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起惠毁，即分而治之）的一個非常典型的應用前鹅。將已有序的子序列合并区赵，得到完全有序的序列愉烙；即先使每個子序列有序减牺，再使子序列段間有序页徐。若將兩個有序表合并成一個有序表苏潜，稱為二路歸并。
1.步奏
（1）將一組數(shù)泞坦，相鄰的兩個分成一組（如最后只剩一個單獨為組）窖贤；
（2）對第一組，申請空間贰锁，使其大小為兩個已經(jīng)排序序列之和赃梧，該空間用來存放合并后的序列；
（3）設定兩個指針豌熄，最初位置分別為兩個已經(jīng)排序序列的起始位置授嘀；
（4）比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間锣险，并移動指針到下一位置蹄皱；
（5）重復步驟（4）直到某一指針超出序列尾；
（6）將另一序列剩下的所有元素直接復制到合并序列尾芯肤；
（7）對每一組進行第一組相同的操作巷折，進行歸并；
（8）對歸并后的組再進行相同操作崖咨，直到歸并成一組有序數(shù)組為止锻拘。
2.舉例
（1）有一組數(shù){30，22，32署拟，41婉宰，18，5推穷，13}心包；
（2）初始狀態(tài)：30，22馒铃，32蟹腾，41，18骗露，5岭佳，13
（3）第一次歸并：{22血巍，30}萧锉，{32，41}述寡，{5柿隙，18}，{13}鲫凶；比較次數(shù)：3禀崖；
（4）第二次歸并：{22，30螟炫，32波附，41}，{5昼钻，13掸屡，18}；比較次數(shù)：4然评；
（5）第三次歸并：{5仅财，13，18碗淌，22盏求，30，32亿眠，41}碎罚；比較次數(shù)：3；
總的比較次數(shù)為：3+4+3=10纳像；
3.復雜度
（1）因為歸并排序的總共的歸并次數(shù)相同荆烈，所以最好、最壞和平均的時間復雜度都為O(nlog?n)爹耗；
（2）空間復雜度為O(n)耙考。
4.穩(wěn)定性
? ? 歸并排序是穩(wěn)定的排序谜喊。在排序過程中，嚴格按照順序進行歸并倦始，相等的元素的順序不會改變斗遏。這對要排序數(shù)據(jù)包含多個信息而要按其中的某一個信息排序,要求其它信息盡量按輸入的順序排列時很重要。
5.性能分析
（1）歸并排序一般適用于用于對總體無序鞋邑，但是各子項相對有序的數(shù)列诵次，這樣比較次數(shù)就會比較少；
（2）歸并排序需要空間來儲存子序列枚碗，比較占用內(nèi)存逾一；
（3）歸并排序的比較次數(shù)小于快速排序的比較次數(shù)，移動次數(shù)一般多于快速排序的移動次數(shù)肮雨，性能稍差于快速排序遵堵。
