2 2 MERGESORT Algorithms F O U R T H R O B E R T S E D G E W I C K Algorithms 4th Edition E D I T I O N K E V I N mergesort bottom up mergesort sorting complexity comparators stability W A Y N E Robert Sedgewick and Kevin Wayne Copyright 2002 2011 October 4 2011 6 22 03 AM Two classic sorting algorithms Critical components in the world s computational infrastructure Full scientific understanding of their properties has enabled us Quicksort honored as one of top 10 algorithms of 20th century to develop them into practical system sorts in 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 2 mergesort bottom up mergesort sorting complexity comparators stability 3 Mergesort Basic plan Divide array into two halves Recursively sort each half Merge two halves input M E R G E S O R T E X A M P L E sort left half E E G M O R R S T E X A M P L E sort right half E E G M O R R S A E E L M P T X merge results A E E E E G L M M O P R R S T X Mergesort overview 4 Merging demo 5 Merging Q How to combine two sorted subarrays into a sorted whole A Use an auxiliary array a k aux 0 1 2 3 4 5 6 7 8 9 input E E G M R A C E R copy E E G M R A C E R merged result 0 1 2 3 4 5 6 7 8 9 T T E E G M R A C E R T A C E R T C E R T 0 A 1 A C 2 A C E 3 A C E E 4 A C E E E 5 A C E E E G 6 A C E E E G M 7 A C E E E G M R 8 A C E E E G M R R 9 A C E E E G M R R T A C E E E G M R R T i j 0 5 0 6 E E G M R 0 7 E E G M R 1 7 E E G M R E R T 2 7 E G M R E R T 2 8 G M R E R T 3 8 G M R R T 4 8 M R R T 5 8 R R T 5 9 R T 6 10 T Abstract in place merge trace 6 Merging Java implementation 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 copy int i lo j mid 1 for int k lo k hi k if i mid else if j hi else if less aux j aux i else assert isSorted a lo hi merge a k a k a k a k aux j aux i aux j aux i postcondition a lo hi sorted lo aux A G L i mid O R hi j H I M S T k a A G H I L M 7 Assertions Assertion Statement to test assumptions about your program Helps detect logic bugs Documents code Java assert statement Throws an exception unless boolean condition is true assert isSorted a lo hi Can enable or disable at runtime No cost in production code java ea MyProgram java da MyProgram enable assertions disable assertions default Best practices Use to check internal invariants Assume assertions will be disabled in production code e g don t use for external argument checking 8 Mergesort Java implementation public 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 lo 10 mid 11 12 13 14 hi 15 16 17 18 19 9 Mergesort trace lo hi merge a 0 0 1 merge a 2 2 3 merge a 0 1 3 merge a 4 4 5 merge a 6 6 7 merge a 4 5 7 merge a 0 3 7 merge a 8 8 9 merge a 10 10 11 merge a 8 9 11 merge a 12 12 13 merge a 14 14 15 merge a 12 13 15 merge a 8 11 15 merge a 0 7 15 0 M E E E E E E E E E E E E E E A 1 E M M G G G G E E E E E E E E E 2 R R G M M M M G G G G G G G G E 3 G G R R R R R M M M M M M M M E 4 E E E E E E E O O O O O O O O E 5 S S S S S S O R R R R R R R R G 6 O O O O O O R R R R R R R R R L a 7 8 R T R T R T R T R T R T S T S T S E S E S A S A S A S A S A M M 9 10 11 12 13 14 15 E X A M P L E E X A M P L E E X A M P L E E X A M P L E E X A M P L E E X A M P L E E X A M P L E E X A M P L E T X A M P L E T A X M P L E E T X M P L E E T X M P L E E T X M P E L E T X E L M P E E L M P T X O P R R S T X Trace of merge results for top down mergesort result after recursive call 10 Mergesort animation 50 random items algorithm position in order current subarray not in order http www sorting algorithms com merge sort 11 Mergesort animation 50 reverse sorted items algorithm position in order current subarray not in order http www sorting algorithms com merge sort 12 Mergesort empirical analysis Running time estimates …
View Full Document
Unlocking...