归并排序（java）

假设初始序列有n个数字，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2（或1）的有序子序列；再两两归并，如此反复即可。时间复杂度O(nlogn)，是稳定的排序算法。非递归实现的性能好于递归的方式。

  8   3   12   5   10
  \  /     \  /    /
 [3 8]   [5 12]  [10]
    \     /       /
   [3 5 8 12]   [10]
       \       /
       [3 5 8 10 12]

代码-递归方式

// 1. 递归算法
void mergeSort(int[] arr) {
    if (arr == null || arr.length <= 0) {
        return;
    }
    int[] tmp = new int[arr.length]; //辅助数组
    mergeSort(arr, tmp, 0, arr.length - 1);
}

void mergeSort(int[] arr, int[] tmp, int start, int end) {
    if (start < end) {
        int middle = start + (end - start) / 2;
        mergeSort(arr, tmp, start, middle);        // 对左边的序列进行归并排序
        mergeSort(arr, tmp, middle + 1, end); //对右边的序列进行归并排序
        merge(arr, tmp, start, middle, end);       // 合并左右两个有序的序列
    }
}

// 将有序的arr[start...middle -1]和arr[middle...end]合并为有序的arr[start...end]
void merge(int[] arr, int[] tmp, int start, int middle, int end){
    if (start >= end) {
        return;
    }
    int i = start;       // 左边序列的索引
    int j = middle + 1;  // 右边序列的索引
    int k = start;       // 合并后有序序列的索引，用tmp来临时保存合并后的有序序列

    while (i <= middle && j <= end) {
        if (arr[i] < arr[j]) {
            tmp[k] = arr[i];
            i++;
        } else {
            tmp[k] = arr[j];
            j++;
        }
        k++;
    }
    if (i <= middle) {
        // 若左边序列还有剩余，则将左边序列剩余数字拷贝到tmp中
        while (i <= middle) {
            tmp[k] = arr[i];
            i++;
            k++;
        }
    } else if (j <= end) {
        // 若右边序列还有剩余，则将右边序列剩余数字拷贝到tmp中
        while (j <= end) {
            tmp[k] = arr[j];
            j++;
            k++;
        }
    }

    // 将tmp里的有序序列拷贝到原始数组中
    for (i = start; i <= end; i++) {
        arr[i] = tmp[i];
    }
}

代码-非递归方式

// 2.非递归算法
void mergeSort2(int[] arr){
    if (arr == null || arr.length <= 0) {
        return;
    }
    int k = 1; // 归并的子序列长度，初始值为1
    int[] tmp = new int[arr.length];
    while (k < arr.length) {
        mergeSort2(arr, tmp, k); // 对长度为k的子序列进行两两归并
        k = k * 2;               // 自序列加倍
    }
}

void mergeSort2(int[] arr, int[] tmp, int k){
    int i = 0;
    while (i + 2 * k <= arr.length) {
        merge(arr, tmp, i, i + k - 1, i + 2 * k - 1); // 分解成两个子序列进行归并
        i = i + 2 * k;
    }

    if (i + k < arr.length) {
        merge(arr, tmp, i, i + k - 1, arr.length - 1); // 归并最后两个子序列
    }
}