归并排序(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;}