归并排序的思路
 
归并排序是通过“归并”操作完成排序的，将两个或者多个有序子表归并成一个子表。归并排序是“分治法”的一个非常典型的应用，同时它也是递归算法的一个好的实例。它将问题分成一些小的问题然后递归求解，而治就是把分阶段的答案拼起来。
 
二路归并排序
 
基本思想 
 二路归并排序就是将两个有序子表归并成一个有序表。首先我们得有一个算法用于归并：两个有序表放在同一数组的相邻位置上，arr[left]到arr[center-1]为第一个有序表，arr[center]到arr[right]是第二个有序表。每次从两段中取出一个进行比较，小的先放入一个temp数组，最后将比较剩下的直接放到temp中去，最后将temp又复制回arr。这是“治”。 
 下面说“分”，只需要递归地将前半部分和后半部分的数据各自归并排序即可。
例子 
 {3,6,1,7,9,4,5,8,2} 
 二路归并排序的过程如图所示： 
 
算法分析 
 每一趟归并的时间复杂度为O(n)，共需要进行⌈log2n⌉趟。对应的算法的时间复杂度为O(nlog2n)。归并排序的空间复杂度O(n)。另外，归并排序中归并的算法并不会将相同关键字的元素改变相对次序，所以归并排序是稳定的。
Java代码实现
 
package com.gray;

import java.util.Arrays;

public class MergeSort {
    public static void main(String args[]) {
        int a[] = {3, 6, 1, 7, 9, 4, 5, 8, 2};
        mergeSort(a);
        System.out.println("排序后：" + Arrays.toString(a));
    }

    private static void mergeSort(int[] arr) {
        mergeSort(arr, new int[arr.length], 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int[] temp, int left, int right) {
        if (left < right) {
            int center = (left + right) / 2;
            mergeSort(arr, temp, left, center); // 左边
            mergeSort(arr, temp, center + 1, right); // 右边
            merge(arr, temp, left, center + 1, right); // 合并两个有序
        }
    }

    /**
     * 将两个有序表归并成一个有序表
     *
     * @param arr
     * @param temp     临时数组
     * @param leftPos  左边开始下标
     * @param rightPos 右边开始下标
     * @param rightEnd 右边结束下标
     */
    private static void merge(int[] arr, int[] temp, int leftPos, int rightPos, int rightEnd) {
        int leftEnd = rightPos - 1; // 左边结束下标
        int tempPos = leftPos; // 从左边开始算
        int numEle = rightEnd - leftPos + 1; // 元素个数
        while (leftPos <= leftEnd && rightPos <= rightEnd) {
            if (arr[leftPos] <= arr[rightPos])
                temp[tempPos++] = arr[leftPos++];
            else
                temp[tempPos++] = arr[rightPos++];
        }
        while (leftPos <= leftEnd) {  // 左边如果有剩余
            temp[tempPos++] = arr[leftPos++];
        }
        while (rightPos <= rightEnd) { // 右边如果有剩余
            temp[tempPos++] = arr[rightPos++];
        }
        // 将temp复制到arr
        for (int i = 0; i < numEle; i++) {
            arr[rightEnd] = temp[rightEnd];
            rightEnd--;
        }
    }
}

写在前面
 
       前面有篇文章已经写了选择类排序、交换类排序和插入类排序（传送门），下面将介绍二路归并排序和基数排序。
 
二路归并排序
 
1、执行过程
 
       原始序列：45 35 65 95 75 15 25
        1）将原始序列看作是7个有序的含有一个关键字的子序列
        子序列1：45
        子序列2：35
        子序列3：65
        子序列4：95
        子序列5：75
        子序列6：15
        子序列7：25
        2）两两归并，形成若干个有序的二元组
        {35，45} ， {65，95} ， {15，75} ， {25}
        3）再将这个序列当作若干个二元组的子序列
        子序列1：35    45
        子序列2：65    95
        子序列3：15    75
        子序列4：25
        4）继续两两归并，形成若干个有序的四元组
        {35，45，65，95} ， {15 ，25 ，75}
        5）最后只剩下两个子序列，再进行一次归并，就完成了整个二路归并排序，结果如下
        15    25    35    65    75    95
 
2、算法代码
 
      由执行过程可知，归并排序可以看作是一个分而治之的过程：先将整个序列分成两半，对每一半分别进行归并排序，将得到两个有序序列，然后将这两个序列合并成一个序列即可。
 
void mergeSort(int R[] , int low , int high){
	if(low < high){
		int mid = (low + high)/2;
		mergeSort(R,low,mid);
		mergeSort(R,mid+1,high);
		merge(R,low,mid,high);//合并算法，将两个有序的序列合并成一段有序序列
	}
}
 
3、性能分析
 
      时间复杂度O(nlogn)，空间复杂度O(n)
 
基数排序
 
1、执行过程
 
      初始桶如下图所示：
       原始序列：78   09   63   30   89   84   05   69   08   83
       1）进行第一趟分配和收集，按最后一位分配，如：
       78的最低位为8，放到桶8中，如下图所示：
 
       09的最低位是9，放到桶9，如下图所示：
 
       依次将原始序列的每个数放到桶中，结果如下图所示：
       然后按照桶0到9的顺序，从桶下面收集关键字，结果为：
         30  63  83  84  05  78  08  09  89  69
       2）在第一趟排序的基础上，进行第二趟分配和收集，按照倒数第二位（本例中是第一位），结果如下图所示：
 
       然后收集，结果为：
         05  08  09  30  63  69  78  83  84  89
       现在最高位有序，最高位相同的关键字最低位有序，于是整个序列有序，基数排序结束。
 
3、性能分析
 
      时间复杂度：O(d(n+r))，空间复杂度O(r），其中，n为序列中关键字的个数，d为关键字的位数，r为关键字基的个数。

最坏时间复杂度O(nlogn) 
 最好时间复杂度O(nlogn)
 
void merge(int *a,int lo,int mi, int hi){
    int nl = mi-lo+1;//左边的长度
    int nr = hi - mi;//右边的长度 

   int *L = new int[nl+1];//空出一个哨兵的位置
   int *R = new int[nr+1];
   L[nl] = 100000;//左边队列的哨兵
   R[nr] = 100000;//右边队列的哨兵
  int i,j,k;
  for(i=0; i<nl; i++){
        L[i] = a[lo+i];//把左边部分的值赋给一个保存左边值的临时队列
    }

    for(j=0; j<nr;j++)
        R[j] = a[mi+1+j];

    //k从lo的位置开始
    for(i =0,j=0,k=lo;k<= hi;k++){
        if(L[i] <= R[j]){//把较小的值赋给主队列
            a[k] =L[i];
            i++;
        }else{
            a[k] = R[j];
            j++;
        }
    }

    delete []L;
    delete []R;
}

void mergeSort(int *a, int lo,int hi){
    if(lo < hi){
        int mi = (lo+hi) >> 1;
        mergeSort(a,lo,mi);
        mergerSort(a,mi+1,hi);
        merge(a,lo,mi,hi);
    }
}

void main(){
    int a[] = {9,8,7,6,5,4,3,2,1};
    int n = sizeof(a)/sizeof(a[0]);
    int lo = 0;
    int hi = n-1;
    mergeSort(a,lo,hi);


}