十大排序算法——归并排序

思想：

（大部分情况）左半边用尽，则取右半边元素；右半边用尽，则取左半边元素；右半边的当前元素小于左半边的当前元素，则取右半边元素；（特殊情况）右半边的当前元素大于左半边的当前元素，则取左半边的元素。实际上大部分发生的都是后面两句话，前面两句只是特殊情况而已。

Java

public class Merge{
    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 5, 8, 9, 0, 7, 5, 1, 6, 8, 7};
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }

    private static void mergeSort(int[] array) {
        int[] aux = new int[array.length];
        sort(array, aux, 0, array.length - 1);
    }

    private static void sort(int[] array, int[] aux, int lo, int hi) {
        if (hi<=lo) return;
        int mid = lo + (hi - lo)/2;
        sort(array, aux, lo, mid);
        sort(array, aux, mid + 1, hi);
        merge(array, aux, lo, mid, hi);
    }

    private static void merge(int[] array, int[] aux, int lo, int mid, int hi) {
        System.arraycopy(array,0,aux,0,array.length);
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i>mid) array[k] = aux[j++];
            else if (j > hi) array[k] = aux[i++];
            else if (aux[j]<aux[i]) array[k] = aux[j++];
            else array[k] = aux[i++];
        }
    }
}

C

void Merge(int low,int high) 
{ 
   if(low>=high)   return;//每个子列表中剩下一个元素时停止 
   else int mid=(low+high)/2;/*将列表划分成相等的两个子列表,若有奇数个元素，则在左边子列表大于右侧子列表*/ 
   MergeSort(low,mid);//子列表进一步划分 
   MergeSort(mid+1,high); 
   int [] B=new int [high-low+1];//新建一个数组，用于存放归并的元素 
   for(int i=low,j=mid+1,k=low;i<=mid && j<=high;k++)/*两个子列表进行排序归并，直到两个子列表中的一个结束*/ 
   { 
       if (arr[i]<=arr[j];) 
{ 
    B[k]=arr[i]; 
    I++; 
} 
else
    { B[k]=arr[j]; j++; } 
} 
for(   ;j<=high;j++,k++)//如果第二个子列表中仍然有元素，则追加到新列表 
      B[k]=arr[j]; 
   for(   ;i<=mid;i++,k++)//如果在第一个子列表中仍然有元素，则追加到新列表中 
      B[k]=arr[i]; 
   for(int z=0;z<high-low+1;z++)//将排序的数组B的 所有元素复制到原始数组arr中 
      arr[z]=B[z]; 
} 

效率：

O（nlogn），归并的最佳、平均和最糟用例效率之间没有差异。
适用于排序大列表，基于分治法。