二路歸并排序的基本思想
設(shè)數(shù)組a中存放了n個(gè)數(shù)據(jù)元素，初始時(shí)把它們看成是n個(gè)長度為1的有序子數(shù)組，然后從第一個(gè)有序子數(shù)組開始，把相鄰的有序子數(shù)組兩兩合并麦备，得到[n/2]個(gè)長度為2的新的有序子數(shù)組（當(dāng)n為奇數(shù)時(shí)，最后一個(gè)新的有序子數(shù)組的長度為1）。對(duì)這些新的有序子數(shù)組再進(jìn)行兩兩歸并凛篙。如此重復(fù)，直到得到一個(gè)長度為n的有序數(shù)組為止栏渺。
一次二路歸并排序算法的目標(biāo)是把若干個(gè)長度為k的相鄰有序子數(shù)組從前呛梆、向后進(jìn)行兩兩歸并，得到個(gè)數(shù)減半的長度為2k的相鄰有序子數(shù)組磕诊。算法設(shè)計(jì)中要考慮的一個(gè)問題是：若元素個(gè)數(shù)為2k的整數(shù)倍填物，則兩兩歸并正好完成n個(gè)數(shù)據(jù)元素的一次二路歸并；若元素個(gè)數(shù)不為2k的整數(shù)倍霎终，則當(dāng)歸并到最后一組時(shí)滞磺，剩余的元素個(gè)數(shù)會(huì)不足2k個(gè)，這時(shí)的處理方法是：
① 若剩余的元素個(gè)數(shù)大于k而小于2k莱褒，則把前k個(gè)元素作為一個(gè)子數(shù)組击困，把剩余的元素作為最后一個(gè)子數(shù)組。
② 若剩余的元素個(gè)數(shù)小于k時(shí)广凸，也即剩余的元素個(gè)數(shù)只夠一組時(shí)阅茶，則不用再進(jìn)行兩兩歸并排序。
二路歸并排序的復(fù)雜度分析
對(duì)n個(gè)元素進(jìn)行一次二路歸并排序時(shí)谅海，歸并的次數(shù)約為lbn脸哀，任何一次的二路歸并排序元素的比較次數(shù)都約為n-1，所以扭吁，二路歸并排序算法的時(shí)間復(fù)雜度為O(nlbn)撞蜂。
二路歸并排序時(shí)使用了n個(gè)臨時(shí)內(nèi)存單元存放數(shù)據(jù)元素，所以侥袜，二路歸并排序算法的空間復(fù)雜度為O(n)蝌诡。
由于二路歸并排序算法是相鄰有序子表兩兩歸并，對(duì)于關(guān)鍵字相同的數(shù)據(jù)元素系馆，能夠保證原來在前邊的元素排序后仍在前邊送漠，因此，二路歸并排序算法是一種穩(wěn)定的排序算法由蘑。
前邊討論過的幾個(gè)時(shí)間復(fù)雜度為O(nlbn)的排序算法都是不穩(wěn)定的排序算法闽寡，而二路歸并排序算法不僅時(shí)間復(fù)雜度是O(nlbn)，而且還是一種穩(wěn)定的排序算法尼酿。這是二路歸并排序算法的最大特點(diǎn)爷狈。
