Merge sort

对一个随机点的链表进行排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

算法描述

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

示例代码

Python

def merge_sort(lst):
    if len(lst) <= 1:
        return lst
 
    def merge(left, right):
        merged = []
        while left and right:
            merged.append(left.pop(0) if left[0] <= right[0] else right.pop(0))
        while left:
            merged.append(left.pop(0))
        while right:
            merged.append(right.pop(0))
        return merged
 
    middle = int(len(lst) / 2)
    left = merge_sort(lst[:middle])
    right = merge_sort(lst[middle:])
    return merge(left, right)

Java

public static int[] mergeSort(int[] arr){//归并排序 --递归
	if(arr.length==1){
		return arr;
	}
	int half = arr.length/2;
	int[] arr1 = new int[half];
	int[] arr2 = new int[arr.length-half];
	System.arraycopy(arr, 0, arr1, 0, arr1.length);
	System.arraycopy(arr, half, arr2, 0, arr2.length);
	arr1 = mergeSort(arr1);
	arr2 = mergeSort(arr2);
	return mergeSortSub(arr1,arr2);
}
 
private static int[] mergeSortSub(int[] arr1,int[] arr2){//归并排序子程序
	int[] result = new int[arr1.length+arr2.length];
	int i = 0;
	int j = 0;
	int k = 0;
	while(true){
		if(arr1[i] < arr2[j]){
			result[k] = arr1[i];
			if(++i>arr1.length-1){
				break;
			}
		}else{
			result[k] = arr2[j];
			if(++j>arr2.length-1){
				break;
			}
		}
		k++;
	}
	for(;i<arr1.length;i++){
		result[++k] = arr1[i];
	}
	for(;j<arr2.length;j++){
		result[++k] = arr2[j];
	}
	return result;
}