1. /** 
    2. *@Description: 归并排序： 
    3. * 假设初始序列含有n个记录，则可以看成是n个有序子序列，每个子序列的长度为1， 
    4. * 然后两两归并，的到[n/2]([x]表示不小于x的最小整数)个长度为2或者为1的有序子序列， 
    5. * 再两两归并，如此重复，直到得到一个长度为n的有序序列为止，这种方法被称为2路归并排序 
    6. *@Author: lizhouwei 
    7. *@CreateDate: 2018/6/23 16:11 
    8. * @Modified By: 
    9. */
    10. public class MergeSort {
    11.     public static void mergeSort(Integer[] arr) {
    12.         if (arr == null || arr.length == 0) {
    13.             return;
    14.         }
    15.         SortUtil.printArray("归并排序前", arr);
    16.         Integer[] res = new Integer[arr.length];
    17.         merge(arr, 0, arr.length - 1, res);
    18.         SortUtil.printArray("归并排序后", arr);
    19.     }
    20.     private static void merge(Integer[] arr, int left, int right, Integer[] res) {
    21.         if (left >= right) {
    22.             return;
    23.         }
    24.         int mid = (left + right) / 2;
    25.         merge(arr, left, mid, res);
    26.         merge(arr, mid + 1, right, res);
    27.         int resleft = left;
    28.         int resright = mid + 1;
    29.         int resK = left;
    30.         while (resleft <= mid && resright <= right) {
    31.             if (arr[resleft] < arr[resright]) {
    32.                 res[resK++] = arr[resleft++];
    33.             } else {
    34.                 res[resK++] = arr[resright++];
    35.             }
    36.         }
    37.         while (resleft <= mid) {
    38.             res[resK++] = arr[resleft++];
    39.         }
    40.         while (resright <= right) {
    41.             res[resK++] = arr[resright++];
    42.         }
    43.         while (--resK >= 0) {
    44.             arr[resK] = res[resK];
    45.         }
    46.     }
    47. }