2.2 Mergesort

归并排序将两个有序的数组归并成成一个更大的数组。

性质：

• 长度为N的数组排序所需时间和NlogN成正比
• 但缺点是所需额外空间和N成正比

所以是典型的以空间换时间的算法。

原地归并的抽象方法

public static void merge(Comparable[] a, int lo, int mid, int hi)
{
	//将a[lo...mid]和a[mid...hi]归并
	int i = lo,j = mid+1;
	//将a[lo...hi]复制到aux[lo...hi]
	for(int k = lo; k <= hi; k++)
		aux[k] = a[k];

	for(int k = lo; k <= hi; k++){
		if     (i > mid)           a[k] = aux[j++];//左边用尽，取右边
		else if(j > hi)            a[k] = aux[i++];//右边用尽，取左边
		else if(less(a[j], a[i]))  a[k] = aux[j++];//相比的两个值，右边小就把右边的放入归并队列
		else                       a[k] = aux[i++];//同理，左边小，就把左边的放入归并序列
	}
}

自顶向下的归并排序

下面这段代码证明了：如果它能将两个子数组排序，它就能够通过归并两个子数组来将

public class Merge{
	private static Comparable[] aux; //归并所需的辅助数组
	public static void sort(){
		aux = new Comparable[a.length];//一次性分配空间
		sort(a, 0, a.length-1);
	}
	public static void sort(Comparable[] a,int lo,int hi){
		if(hi < lo) return;
		int mid = lo + (hi-lo)/2;
		sort(a, lo, mid);          //将左半边排序
		sort(a, mid+1, hi);        //将右半边排序
		merge(a, lo, mid, hi);     //归并结果
	}
}

sort()方法的作用在于安排多次merge()方法的调用顺序。
归并排序所需的时间和NlgN成正比，只需要比遍历数组多个对数因子的时间就能将一个庞大的数组排序。
缺点是辅助数组所使用的额外空间和N的大小成正比。
改进：

• 对小规模子数组使用插入排序
• 测试数组是否有序
• 不将元素复制到辅助数组

MergeX.java implements these improvements.

自底向上的归并序列

public class MergeBU{
	private static Comparable[] aux; //归并所需辅助数组
	public static void sort(Comparable[] a){
		int N = a.length;
		aux = new Comparable[N];
		for(int sz = 1;sz < N;sz = sz + sz) //sz子数组大小
			for(int lo = 0;lo < N-sz;lo += sz+sz) //lo：子数组索引
				merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
	}
}

自底向上的归并排序比较适合用链表组织的数据。
归并排序是一种渐进最优的基于比较排序的算法。

Creative Problems

1. Faster merge. Implement a version of merge() that copies the second half of a[] to aux[] in decreasing order and then does the merge back to a[]. This change allows you to remove the code to test that each of the halves has been exhausted from the inner loop. Note: the resulting sort is not stable.

   private static void merge(Comparable[] a, int lo, int mid, int hi){
       for(int i=lo; i <= mid; i++)
           aux[i] =a[i];
   
       for(int j = mid+1; j <= hi; j++)
           aux[j] = a[hi-j+mid+1];
       int i = lo,j = hi;
       for(int k = lo;k <= hi;k++)
           if(less(aux[j],aux[i])) a[k] = aux[j--];
           else                    a[k] = aux[i++];
   }
   

2. Improvements. Write a program MergeX.java that implements the three improvements to mergesort that are described in the text: add a cutoff from small subarrays, test whether the array is already in order, and avoid the copy by switching arguments in the recursive code.

3. Inversions. Develop and implement a linearithmic algorithm Inversions.java for computing the number of inversions in a given array (the number of exchanges that would be performed by insertion sort for that array—see Section 2.1). This quantity is related to the Kendall tau distance; see Section 2.5.
   Web Exercise(N)

---