归并排序(Merge Sort)采用的是经典的分治思想，分治法将序列递归地把平均分割成两半，在保持元素顺序的同时将上一步得到的子序列集成到一起。

算法特性

• 稳定性

归并排序是一种稳定的排序算法。

• 时间复杂度

归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。。

• 空间复杂度

归并排序的排序在每一次合并时需要额外的空间，临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

算法步骤

1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

2.设定两个指针，最初位置分别为两个已经排序序列的起始位置

3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

4.重复步骤3直到某一指针到达序列尾

5.将另一序列剩下的所有元素直接复制到合并序列尾

动画演示

代码实现

Java代码:

public static int[] mergeSort(int[] sourceArray) {
    if (sourceArray == null || sourceArray.length < 2) {
        return sourceArray;
    }

    int length = sourceArray.length;
    int[] array = Arrays.copyOf(sourceArray, length);
    process(array, 0, length - 1);

    return array;
}

public static void process(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }

    int mid = left + ((right - left) >> 2);
    process(array, left, mid);
    process(array, mid + 1, right);
    partition(array, left, mid, right);
}

public static void partition(int[] array, int left, int mid, int right) {
    int[] help = new int[right - left + 1];
    int p1 = left;
    int p2 = mid + 1;
    int index = 0;
    while (p1 <= mid && p2 <= right) {
        help[index++] = array[p1] > array[p2] ? array[p2++] : array[p1++];
    }

    while (p1 <= mid) {
        help[index++] = array[p1++];
    }

    while (p2 <= right) {
        help[index++] = array[p2++];
    }

    for (int i = 0; i < help.length; i++) {
        array[left + i] = help[i];
    }
}

private static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}