归并排序的基本思想是：将两个（或以上）的有序表组成新的有序表。

更实际的意义：可以把一个长度为n的无序序列看成是n个长度为1的有序子序列，首先做两两归并，得到个长度为2的子序列；再做两两归并，...，如此重复，直到最后得到一个长度为n的有序序列。

例：关键字序列T=(21, 25, 49, 25*, 93, 62, 72, 08, 37, 16, 54)，请给出归并排序的具体实现过程。

len = 1 :  21， 25， 49， 25*，93， 62， 72， 08， 37， 16， 54

len = 2：21  25， 25* 49， 62 93， 08 72， 16 37， 54

len = 4：21 25 25* 49， 08 62 72 93， 16 37 54

len = 8：08 21 25 25* 49 62 72 93， 16 37 54

len = 16：08 16 21 25 25* 37 49 54 62 72 93

整个归并排序仅需。

归并排序实现的代码：

public class arrayMergeSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = {21, 25, 49, 25, 93, 62, 72, 8, 37, 16, 54};
		mergeSort(arr, 0, arr.length - 1);
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i]+" ");
		}
	}
	
	public static void mergeSort(int[] array, int low, int high) {
		int mid = (low + high) / 2;
		if(low < high) {
			// 左边
			mergeSort(array, low, mid);
			// 右边
			mergeSort(array, mid + 1, high);
			// 左右归并
			merge(array, low, mid, high);
		}
		
	}
	
	public static void merge(int[] array, int low, int mid, int high) {
	       int[] temp = new int[high - low + 1];
	        int i = low;// 左指针
	        int j = mid + 1;// 右指针
	        int k = 0;
	        // 把较小的数先移到新数组中
	        while (i <= mid && j <= high) {
	            if (array[i] < array[j]) {
	                temp[k++] = array[i++];
	            } else {
	                temp[k++] = array[j++];
	            }
	        }
	        // 把左边剩余的数移入数组
	        while (i <= mid) {
	            temp[k++] = array[i++];
	        }
	        // 把右边边剩余的数移入数组
	        while (j <= high) {
	            temp[k++] = array[j++];
	        }
	        // 把新数组中的数覆盖nums数组
	        for (int k2 = 0; k2 < temp.length; k2++) {
	        	array[k2 + low] = temp[k2];
	        }
	}

}

归并排序算法分析：

• 时间效率：O（nlog2n）

一趟归并排序的操作是：调用【n / 2h】次算法merge将数组中前后相邻且长度为h的有序段进行两两归并，得到前后相邻长度为2h的有序段，并存放在辅助数组中，整个归并排序需要进行【log2n】趟，所以算法总的时间复杂度为O(nlog2n)。

• 空间效率：O（n）

因为需要一个与原始序列同样大小的辅助序列。这正是此算法的缺点。

• 稳定性：稳定

归并排序的Python实现：

class Solution:

    def mergeSort(self, array, low, high):
        mid = (low + high) // 2
        if low < high:
            # 左边
            self.mergeSort(array, low, mid)
            # 右边
            self.mergeSort(array, mid + 1, high)

            # 左右合并
            temp = [0] * (high - low + 1)
            # 左指针
            i = low
            # 右指针
            j = mid + 1
            k = 0
            # 把较小的数先移到新数组中
            while i <= mid and j <= high:
                if array[i] < array[j]:
                    temp[k] = array[i]
                    k += 1
                    i += 1
                else:
                    temp[k] = array[j]
                    k += 1
                    j += 1

            # 把左边剩余的数移入数组中
            while i <= mid:
                temp[k] = array[i]
                k += 1
                i += 1

            # 把右边剩余的数移入到数组中
            while j <= high:
                temp[k] = array[j]
                k += 1
                j += 1

            for i in range(0, len(temp)):
                array[i + low] = temp[i]

        return array


if __name__ == "__main__":
    array = [7, 5, 6, 4]
    sol = Solution()
    print(sol.mergeSort(array, 0, len(array) - 1))