Algorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2008·February 15, 2009 11:15:13 AMMergesort!mergesort!sorting complexity!comparatorsReference: Algorithms in Java. 4th Edition, Section 3.2 http://www.cs.princeton.edu/algs4Except as otherwise noted, the content of this presentationis licensed under the Creative Commons Attribution 2.5 License.2Two 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 overview5Mergesort 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 hiGoal. Combine two sorted subarrays into a sorted whole.Q. How to merge efficiently? 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 Mijklohimaux[]a[]public static void merge(Comparable[] a, int lo, int mid, int hi){ // Merge a[lo..m] with a[m+1..hi]. for (int k = lo; k < hi; k++) aux[k] = a[k]; int i = lo, j = mid; 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++];} copymerge8Mergesort: Java implementationlom 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, mid, hi); } public static void sort(Comparable[] a) { aux = new Comparable[a.length]; sort(a, 0, a.length - 1); }}9Mergesort visualizationVisual trace of top-down mergesort with cutoff for small subfilesfirst subfilesecond subfilefirst mergefirst half sortedsecond half sortedresult10Mergesort animationmerge in progress output auxiliary arraydone merge in progress inputuntouched11Mergesort animation12Mergesort: 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 ~ N lg N compares to sort any array of size N.Def. T(N) = number of compares to mergesort an array of size N. = T(N / 2) + T(N / 2) + NMergesort recurrence. T(N) = 2 T(N / 2) + N for N > 1, with T(1) = 0.•Not quite right for odd N.•Same recurrence holds for many divide-and-conquer algorithms.Solution. T(N) ~ 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. T(N) = 2 T(N / 2) + N for N > 1, with T(1) = 0.Proposition. If N is a power of 2, then T(N) = N lg N.Pf.14Mergesort recurrence: proof 1T(N)T(N/2)T(N/2)T(N/4)T(N/4)T(N/4) T(N/4)T(2) T(2)T(2) T(2) T(2) T(2) T(2)NT(N / 2k)2 (N/2)2k (N/2k)N/2 (2)...lg NN lg N= N= N= N= N...T(2)4 (N/4)= NMergesort recurrence. T(N) = 2 T(N / 2) + N for N > 1, with T(1) = 0.Proposition. If N is a power of 2, then T(N) = N lg N.Pf. 15Mergesort recurrence: proof 2 T(N) = 2 T(N/2) + NT(N) / N = 2 T(N/2) / N + 1 = T(N/2)
View Full Document
Unlocking...