Algorithms, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2002–2012·February 19, 2012 5:27:18 AMAlgorithmsFOUR T H EDIT IONR O B E R T S EDG EWICK K EVIN W A Y N E2.2 MERGESORT‣mergesort‣bottom-up mergesort‣sorting complexity‣comparators‣stability2Two 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. [this lecture]•Java sort for objects.•Perl, C++ stable sort, Python stable sort, Firefox JavaScript, ...Quicksort. [next lecture]•Java sort for primitive types. •C qsort, Unix, Visual C++, Python, Matlab, Chrome JavaScript, ...‣mergesort‣bottom-up mergesort‣sorting complexity ‣comparators‣stability3Basic 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 overview5Merging demoQ. How to combine two sorted subarrays into a sorted whole. A. Use an auxiliary array.6Merging 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 result7Merging: Java implementationA G L O R H I M S TA G H I L Mijklohimidaux[]a[]private static void merge(Comparable[] a, Comparable[] aux, 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 true.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 (so do not use for external argument-checking).8Assertionsassert isSorted(a, lo, hi);java -ea MyProgram // enable assertionsjava -da MyProgram // disable assertions (default)9Mergesort: Java implementationlomid hi10 11 12 13 14 15 16 17 18 19public class Merge{ private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) { /* 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); }}10Mergesort: 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: animation11http://www.sorting-algorithms.com/merge-sort50 random itemsin ordercurrent subarrayalgorithm positionnot in orderMergesort: animation12http://www.sorting-algorithms.com/merge-sort50 reverse-sorted itemsin ordercurrent subarrayalgorithm positionnot in orderMergesort: Transylvanian-Saxon folk dance1314Mergesort: empirical analysisRunning time estimates:•Laptop executes 108 compares/second.•Supercomputer executes 1012 compares/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 weekinstantinstantinstantProposition. Mergesort uses at most N lg N compares and 6 N lg N array accesses to sort any array of size N.Pf sketch. The number of compares C (N) and array accesses A (N)to mergesort an array of size N satisfy the
View Full Document
Unlocking...