归并排序算法是基于归并（Merge）操作的一种有效排序算法，是采用分治法（Divide and Conquer）的典型应用。归并排序算法将待排序序列分为若干个子序列，先对每个子序列进行排序，等每个子序列都有序后，再将有序子序列合并为整体的有序序列。若将两个有序表合并成一个有序表，则称之为二路归并。

5.6.1 归并排序算法的原理

归并排序的原理是先将原始数组分解为多个子序列，然后对每个子序列进行排序，最后将排好序的子序列合并起来。如图5-8所示为对数组[4,1,3,9,6,8]进行归并排序，先经过两次分解，将数组分解成4个子序列，然后对子序列数组进行排序和归并，最终得到排好序的数组[1,3,4,6,8,9]。

5.6.2 归并排序算法的Java实现

归并排序算法的Java实现如下：

public  static  int[]  mergeSort(int[]  data)  {
    sort(data,  0,  data.length  -  1);
    return  data;
}
//对左右两边的数据进行递归
public  static  void  sort(int[]  data,  int  left,  int  right)  {
    if  (left  >=  right)
      return;
    //找出中间索引
    int  center  =  (left  +  right)  /  2;
    //对左边的数组进行递归
    sort(data,  left,  center);
    //对右边的数组进行递归
    sort(data,  center  +  1,  right);
    //将两个数组进行归并
    merge(data,  left,  center,  right);
}
/＊＊
 ＊ 将两个数组进行归并：两个数组在归并前是有序数组，在归并后依然是有序数组
 ＊ @param data：数组对象；left：左边数组第1个元素的索引；
 ＊            center左边数组最后一个元素的索引，center+1是右边数组第1个元素的索引
 ＊            right：右边数组最后一个元素的索引
 ＊/
public  static  void  merge(int[]  data,  int  left,  int  center,  int  right)  {
    //临时数组
    int[]  tmpArr  =  new  int[data.length];
    //右边数组第1个元素的索引
    int  mid  =  center  +  1;
    //third记录临时数组的索引
    int  third  =  left;
    //缓存左边数组第1个元素的索引
    int  tmp  =  left;
    while  (left  <=  center  &&  mid  <=  right)  {
      //从两个数组中取出最小的值放入临时数组中
      if  (data[left]  <=  data[mid])  {
          tmpArr[third++]  =  data[left++];
      }  else  {
          tmpArr[third++]  =  data[mid++];
      }
    }
    //将剩余部分依次放入临时数组（实际上两个while只会执行其中一个）中
    while  (mid  <=  right)  {
        tmpArr[third++]  =  data[mid++];
    }
    while  (left  <=  center)  {
        tmpArr[third++]  =  data[left++];
    }
    //将临时数组中的内容复制到原数组中
    //（原left-right范围内的内容被复制到原数组中）
    while  (tmp  <=  right)  {
        data[tmp]  =  tmpArr[tmp++];
    }
}

以上代码定了3个方法：mergeSort()是归并排序方法的入口；sort()对数据进行递归拆解和合并；merge()进行数据排序和合并。其中，sort()每次都将数组进行二分拆解，然后对左侧的数组和右侧的数据分别进行递归。merge()先将数组进行冒泡排序，然后依次将冒泡排序的结果放入临时数组中，最后将排好序的临时数组放入排序数组中。