Mergesort

Algorithm: Goal. Given two sorted subarrays a[lo] to a[mid] and a[mid+1] to a[hi], replace with sorted subarray a[lo] to a[hi]. public class Merge { private static void merge(...) { /* as before */ } private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; sort(a, aux, lo, mid); sort(a, aux, mid+1, hi); merge(a, aux, lo, mid, hi); } public static void sort(Comparable[] a) { aux = new Comparable[a.length]; sort(a, aux, 0, a.length - 1); } }

Improvements: 1)Use insertion sort for small subarrays. ・Mergesort has too much overhead for tiny subarrays. ・Cutoff to insertion sort for ≈ 7 items. 2)Stop if already sorted. ・Is biggest item in first half ≤ smallest item in second half? ・Helps for partially-ordered arrays. 3)Eliminate the copy to the auxiliary array. Save time (but not space) by switching the role of the input and auxiliary array in each recursive call.

Complexity: Proposition. Any compare-based sorting algorithm must use at least lg ( N ! ) ~ N lg N compares in the worst-case. Bottom Up Mergesort: Stability: Q. Which sorts are stable? A. Insertion sort and mergesort (but not selection sort or shellsort).