Algorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2009·January 22, 2010 2:31:50 PM2.2 Mergesort‣mergesort‣bottom-up mergesort‣sorting complexity‣comparators2Two classic sorting algorithmsCritical components in the world’s computational infrastructure.•Full scientific understanding of their properties has enabled usto develop them into practical system sorts.•Quicksort honored as one of top 10 algorithms of 20th centuryin science and engineering.Mergesort.•Java sort for objects.•Perl, Python stable sort.Quicksort.•Java sort for primitive types. •C qsort, Unix, g++, Visual C++, Python.todaynext lecture‣mergesort‣bottom-up mergesort‣sorting complexity ‣comparators3Basic plan.•Divide array into two halves.•Recursively sort each half.•Merge two halves.4MergesortM E R G E S O R T E X A M P L EE E G M O R R S T E X A M P L EE E G M O R R S A E E L M P T XA E E E E G L M M O P R R S T Xinputsort left halfsort right halfmerge resultsMergesort overviewQ. How to combine two sorted subarrays into a sorted whole. A. Use an auxiliary array.5Merging a[] aux[]k 0 1 2 3 4 5 6 7 8 9 i j 0 1 2 3 4 5 6 7 8 9 E E G M R A C E R T - - - - - - - - - - E E G M R A C E R T E E G M R A C E R T 0 50 A 0 6 E E G M R A C E R T1 A C 0 7 E E G M R C E R T 2 A C E 1 7 E E G M R E R T 3 A C E E 2 7 E G M R E R T 4 A C E E E 2 8 G M R E R T 5 A C E E E G 3 8 G M R R T 6 A C E E E G M 4 8 M R R T 7 A C E E E G M R 5 8 R R T 8 A C E E E G M R R 5 9 R T 9 A C E E E G M R R T 6 10 T A C E E E G M R R T inputcopyAbstract in-place merge tracemerged result6Merging: Java implementationA G L O R H I M S TA G H I L Mijklohimidaux[]a[]private static void merge(Comparable[] a, int lo, int mid, int hi){ assert isSorted(a, lo, mid); // precondition: a[lo..mid] sorted assert isSorted(a, mid+1, hi); // precondition: a[mid+1..hi] sorted for (int k = lo; k <= hi; k++) aux[k] = a[k]; int i = lo, j = mid+1; 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(aux[j], aux[i])) a[k] = aux[j++]; else a[k] = aux[i++]; } assert isSorted(a, lo, hi); // postcondition: a[lo..hi] sorted} copymergeAssertion. Statement to test assumptions about your program.•Helps detect logic bugs.•Documents code.Java assert statement. Throws an exception unless boolean condition is ture.Can enable or disable at runtime. ! No cost in production code. Best practices. Use to check internal invariants. Assume assertions will be disabled in production code (e.g., don't use for external argument-checking).7Assertionsassert isSorted(a, lo, hi);java -ea MyProgram // enable assertionsjava -da MyProgram // disable assertions (default)8Mergesort: Java implementationlomid hi10 11 12 13 14 15 16 17 18 19public class Merge{ private static Comparable[] aux; private static void merge(Comparable[] a, int lo, int mid, int hi) { /* as before */ } private 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, m, hi); } public static void sort(Comparable[] a) { aux = new Comparable[a.length]; sort(a, 0, a.length - 1); }}9Mergesort traceresult after recursive callTrace of merge results for top-down mergesort a[] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 M E R G E S O R T E X A M P L E merge(a, 0, 0, 1) E M R G E S O R T E X A M P L E merge(a, 2, 2, 3) E M G R E S O R T E X A M P L E merge(a, 0, 1, 3) E G M R E S O R T E X A M P L E merge(a, 4, 4, 5) E G M R E S O R T E X A M P L E merge(a, 6, 6, 7) E G M R E S O R T E X A M P L E merge(a, 4, 5, 7) E G M R E O R S T E X A M P L E merge(a, 0, 3, 7) E E G M O R R S T E X A M P L E merge(a, 8, 8, 9) E E G M O R R S E T X A M P L E merge(a, 10, 10, 11) E E G M O R R S E T A X M P L E merge(a, 8, 9, 11) E E G M O R R S A E T X M P L E merge(a, 12, 12, 13) E E G M O R R S A E T X M P L E merge(a, 14, 14, 15) E E G M O R R S A E T X M P E L merge(a, 12, 13, 15) E E G M O R R S A E T X E L M P merge(a, 8, 11, 15) E E G M O R R S A E E L M P T X merge(a, 0, 7, 15) A E E E E G L M M O P R R S T X lo hiMergesort animation10http://www.sorting-algorithms.com/merge-sort50 random elementsin ordercurrent subarrayalgorithm positionnot in orderMergesort animation11http://www.sorting-algorithms.com/merge-sort50 reverse-sorted elementsin ordercurrent subarrayalgorithm positionnot in order12Mergesort: empirical analysisRunning time estimates:•Home pc executes 108 comparisons/second.•Supercomputer executes 1012 comparisons/second.Bottom line. Good algorithms are better than supercomputers.insertion sort (Ninsertion sort (Ninsertion sort (N2)mergesort (N log N)mergesort (N log N)mergesort (N log N)computerthousandmillionbillionthousandmillionbillionhomeinstant2.8 hours317 yearsinstant1 second18 minsuperinstant1 second1 weekinstantinstantinstant13Mergesort: mathematical analysisProposition. Mergesort uses ~ 2 N lg N data moves to sort any array of size N.Def. D(N) = number of data moves to mergesort an array of size N. = D(N / 2) + D(N / 2) + 2 NMergesort recurrence. D(N) = 2 D(N / 2) + 2 N for N > 1, with T(1) = 0.•Not quite right for odd N.•Similar recurrence holds for many divide-and-conquer algorithms.Solution. D(N) ~ 2 N lg N.•For simplicity, we'll prove when N is a power of 2.•True for all N. [see COS 340]left half right half mergeMergesort recurrence.
View Full Document