算法导论 归并排序

问题描述写在了代码中，注释可以帮助理解

import java.util.ArrayList;

/**
 * @author xusulong
 * merge sort
 * 分解：将n个元素分成各含/2个元素的子序列
 * 解决：用merge sort对两个子序列递归地排序
 * 合并：合并两个已排序的子序列以得到排序结果
 */
public class MergeSort {
	private final static int max = 1000000;
	/**
	 * 对子数组A[p...r]进行排序
	 * @param A
	 * @param p
	 * @param r
	 */
	public static void mergeSort(ArrayList<Integer> A, int p, int r) {
		//当p = r 时候数组中只有一个元素，不需要排序，而p不可能大于r
		if(p < r) {
			int q = (p + r)/2;
			mergeSort(A, p, q);
			mergeSort(A, q + 1, r);
			merge(A, p, q, r);
		}
	}
	/**
	 * 
	 * @param A 数组
	 * @param p 下标
	 * @param q 下标
	 * @param r 下标
	 * 假设子数组a[p...q]和a[q + 1...r]已经排序好 p <= q < r
	 */
	public static void merge(ArrayList<Integer> A, int p, int q, int r) {
		//length of the child array
		int n1 = q - p + 1;
		int n2 = r - q;
		//create arrays L[1...n1 + 1] and R[1...n2 + 1]
		ArrayList<Integer> L = new ArrayList<Integer>(n1 + 1);
		ArrayList<Integer> R = new ArrayList<Integer>(n2 + 1);
		for(int i = 0; i < n1; i ++) {
			L.add(A.get(p + i));
		}
		L.add(max);
		
		for(int i = 0; i < n2; i ++) {
			R.add(A.get(q + i + 1));
		}
		R.add(max);
		
		for (int i = 0, j = 0, k = p; k <= r; k ++) {
			if (L.get(i) <= R.get(j)) {
				A.set(k, L.get(i));
				i ++;
			} else {
				A.set(k, R.get(j));
				j ++;
			}
		}
	}
	
	public static void main(String[] args) {
		ArrayList<Integer> A = new ArrayList<Integer>();
		A.add(4);
		A.add(2);
		A.add(5);
		A.add(7);
		A.add(0);
		A.add(3);
		A.add(1);
		A.add(6);
		mergeSort(A, 0, A.size() - 1);
		System.out.println(A);
	}
}

 时间复杂度cnlog2n + cn 为 O(nlog2n)