歸并排序在對(duì)數(shù)組排序的過(guò)程中托启，現(xiàn)遞歸的分為兩半排序宅倒，再將結(jié)果歸并起來(lái)。
實(shí)現(xiàn)歸并的一種直截了當(dāng)?shù)姆绞绞菍蓚€(gè)不同的有序數(shù)組歸并到第三個(gè)數(shù)組屯耸，但是當(dāng)用歸并對(duì)大數(shù)組排序時(shí)拐迁，我們往往需要很多次歸并，因此在每次歸并時(shí)都創(chuàng)建一個(gè)新數(shù)組來(lái)存儲(chǔ)排序結(jié)果會(huì)帶來(lái)問(wèn)題疗绣。因此我們希望可以實(shí)現(xiàn)原地的歸并排序算法线召，在數(shù)組中移動(dòng)而不需要額外的空間。
public static void merge(Comparable[] a, int lo, int mid, int hi){
int i=lo, j=mid+1;
for( int k = lo; k<=hi; k++) //將數(shù)組a復(fù)制到數(shù)組aux
aux[k] = a[k];
for(int k = lo; k<=hi; k++) //歸并回到數(shù)組a
if (i>mid) a[k] = aux[j++];
else if (j>hi) a[k] = aux[i++];
else if(less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = a[i++];
}
以上代碼為抽象化的原地歸并多矮，而通過(guò)分治思想缓淹，可以基于這種原地歸并的抽象實(shí)現(xiàn)自頂向下的歸并排序：
public class Merge{
private static Comparable[] aux; //歸并所需的輔助數(shù)組
private static void sort(Comparable[] a){ //一次性分配空間
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi){
if( hi<= lo) return;
int mid = lo +(hi-lo)/2;
sort(a, lo, mid); //左半側(cè)排序
sort(a, mid+1, hi); //右半側(cè)排序
merge(a, lo, mid, hi); //歸并結(jié)果
}
}
針對(duì)自頂向下的歸并排序，可以證明以下命題:
對(duì)于長(zhǎng)度為N的任意數(shù)組塔逃，自頂向下的歸并排序需要1/2NlgN到NlgN次比較,且最多需要訪問(wèn)數(shù)組6NlgN次讯壶。
通過(guò)上述命題我們知道，歸并排序所需要的時(shí)間和NlgN成正比湾盗，相較于插入排序或是選擇排序有了很大提升伏蚊；而它的主要缺點(diǎn)是所使用的額外空間與和數(shù)組大小N成正比。
實(shí)現(xiàn)歸并的另一種方法是先歸并那些微型數(shù)組格粪，然后再成對(duì)歸并得到子數(shù)組躏吊，并最終將整個(gè)數(shù)組歸并在一起肺孵。這種自底向上的歸并排序相比原先的歸并排序代碼量更小。首先我們兩兩歸并颜阐，然后四四歸并平窘，并一直下去。
public class MergeBU{
private static Comparable[] aux;
public static void sort(Comparable[] a){
int N = a.length;
aux = new Comparable[N];
for( int sz = 1; sz < N; sz = sz+sz)
for(int lo = 0; lo < N-sz; lo+= sz+sz)
merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}
}
當(dāng)數(shù)組長(zhǎng)度為2的冪時(shí)凳怨，自頂向下和自底向上的歸并排序所用的比較次數(shù)和數(shù)組訪問(wèn)次數(shù)是一樣的瑰艘，只是順序不同。
自底向上的歸并排序比較適合用鏈表組織的數(shù)據(jù)肤舞。鏈表先按大小為1的子鏈表進(jìn)行排序紫新，然后是大小為2的…… ** 這種方法不需要?jiǎng)?chuàng)建任何新的結(jié)點(diǎn)，只需要重新組織鏈表連接就能將鏈表原地排序 **
無(wú)論是選擇李剖，插入芒率，希爾還是歸并算法，都是基于比較的算法篙顺，它們對(duì)于數(shù)組的操作是由主鍵比較決定的偶芍。一個(gè)基于比較的算法在兩次比較之間可能會(huì)進(jìn)行任意規(guī)模的計(jì)算，但它只能通過(guò)比較來(lái)獲得某個(gè)主鍵的信息德玫。
針對(duì)基于比較的排序算法匪蟀，我們有以下命題
沒(méi)有任何基于比較的算法能夠保證使用少于lg(N!) ~ NlgN次比較將長(zhǎng)度為N的數(shù)組排序
