Use insertion sort for small subarrays.
Stop if already sorted.
Eliminate the copy to the auxiliary array.
1 | private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) { |
Basic plan.
empirical analysis
Best case. Number of compares is ~ N lg N.
Worst case. Number of compares is ~ ½ N 2 .
Average case. Number of compares is ~ 1.39 N lg N.
Improvements
Best choice of pivot item = median.
Estimate true median by taking median of sample.
Median-of-3 (random) items.
1 | int m = medianOf3(a, lo, lo + (hi - lo)/2, hi); |
1 | private static void sort(Comparable[] a, int lo, int hi) { |