Question? Leave a message!




Merge sort

Merge sort
ECE 250 Algorithms and Data Structures Merge sort Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Merge sort 2 Outline This topic covers merge sort – A recursive divideandconquer algorithm – Merging two lists – The merge sort algorithm – A runtime analysisMerge sort 3 8.5 Merge Sort The merge sort algorithm is defined recursively: – If the list is of size 1, it is sorted—we are done; – Otherwise: • Divide an unsorted list into two sublists, • Sort each sublist recursively using merge sort, and • Merge the two sorted sublists into a single sorted list This is the first significant divideandconquer algorithm we will see Question: How quickly can we recombine the two sublists into a single sorted listMerge sort 4 8.5.1 Merging Example Consider the two sorted arrays and an empty array Define three indices at the start of each arrayMerge sort 5 8.5.1 Merging Example We compare 2 and 3: 2 3 – Copy 2 down – Increment the corresponding indicesMerge sort 6 8.5.1 Merging Example We compare 3 and 7 – Copy 3 down – Increment the corresponding indicesMerge sort 7 8.5.1 Merging Example We compare 5 and 7 – Copy 5 down – Increment the appropriate indicesMerge sort 8 8.5.1 Merging Example We compare 18 and 7 – Copy 7 down – Increment...Merge sort 9 8.5.1 Merging Example We compare 18 and 12 – Copy 12 down – Increment...Merge sort 10 8.5.1 Merging Example We compare 18 and 16 – Copy 16 down – Increment...Merge sort 11 8.5.1 Merging Example We compare 18 and 33 – Copy 18 down – Increment...Merge sort 12 8.5.1 Merging Example We compare 21 and 33 – Copy 21 down – Increment...Merge sort 13 8.5.1 Merging Example We compare 24 and 33 – Copy 24 down – Increment...Merge sort 14 8.5.1 Merging Example We would continue until we have passed beyond the limit of one of the two arrays After this, we simply copy over all remaining entries in the non empty arrayMerge sort 15 8.5.1.1 Merging Two Lists Programming a merge is straightforward: – the sorted arrays, array1 and array2, are of sizen1 and n2, respectively, and – we have an empty array, arrayout, of size n1 + n2 Define three variables int i1 = 0, i2 = 0, k = 0; which index into these three arraysMerge sort 16 8.5.1.1 Merging Two Lists We can then run the following loop: include cassert //... int i1 = 0, i2 = 0, k = 0; while ( i1 n1 i2 n2 ) if ( array1i1 array2i2 ) arrayoutk = array1i1; ++i1; else assert( array1i1 = array2i2 ); arrayoutk = array2i2; ++i2; ++k; Merge sort 17 8.5.1.1 Merging Two Lists We’re not finished yet, we have to empty out the remaining array for ( ; i1 n1; ++i1, ++k ) arrayoutk = array1i1; for ( ; i2 n2; ++i2, ++k ) arrayoutk = array2i2; Merge sort 18 8.5.1.2 Analysis of merging The statement ++out will only be run at most n + n times 1 2 – Therefore, the body of the loops run a total of n + n times 1 2 – Hence, merging may be performed in Q(n + n ) time 1 2 If the arrays are approximately the same size, n = n and n ≈ n , we 1 1 2 can say that the run time is Q(n) Problem: We cannot merge two arrays inplace – This algorithm always required the allocation of a new array – Therefore, the memory requirements are also Q(n)Merge sort 19 8.5.2 The Algorithm The algorithm: – Split the list into two approximately equal sublists – Recursively call merge sort on both sub lists – Merge the resulting sorted listsMerge sort 20 8.5.2 The Algorithm Recall the five sorting techniques: – Insertion – Exchange – Selection – Merging – Distribution Clearly merge sort falls into the fourth categoryMerge sort 21 8.5.2 The Algorithm Question: – we split the list into two sublists and sorted them – how should we sort those lists Answer (theoretical): – if the size of these sublists is 1, use merge sort again – if the sublists are of length 1, do nothing: a list of length one is sortedMerge sort 22 8.5.2 The Algorithm However, just because an algorithm has excellent asymptotic properties, this does not mean that it is practical at all levels Answer (practical): – If the sublists are less than some threshold length, use an algorithm like insertion sort to sort the lists – Otherwise, use merge sort, againMerge sort 23 8.5.3 Implementation Suppose we already have a function template typename Type void merge( Type array, int a, int b, int c ); that assumes that the entries arraya through arrayb 1, and arrayb through arrayc 1 are sorted and merges these two subarrays into a single sorted array from index a through index c 1, inclusiveMerge sort 24 8.5.3 Implementation For example, given the array, 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 13 77 49 35 61 3 23 48 73 89 95 17 32 37 57 94 99 28 15 55 7 51 88 97 62 a call to void merge( array, 14, 20, 26 ); merges the two sublists 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 13 77 49 35 61 3 23 48 73 89 95 17 32 37 57 94 99 28 15 55 7 51 88 97 62 forming 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 13 77 49 35 61 3 17 23 32 37 48 57 73 89 94 95 99 28 15 55 7 51 88 97 62Merge sort 25 8.5.3 Implementation We will therefore implement a function template typename Type void mergesort( Type array, int first, int last ); that will sort the entries in the positions first = i and i last – If the number of entries is less than N, call insertion sort – Otherwise: • Find the midpoint, • Call merge sort recursively on each of the halves, and • Merge the resultsMerge sort 26 8.5.3 Implementation The actual body is quite small: template typename Type void mergesort( Type array, int first, int last ) if ( last first = N ) insertionsort( array, first, last ); else int midpoint = (first + last)/2; mergesort( array, first, midpoint ); mergesort( array, midpoint, last ); merge( array, first, midpoint, last ); Merge sort 27 8.5.3 Implementation Like merge sort, insertion sort will sort a subrange of the array: template typename Type void insertionsort( Type array, int first, int last ) for ( int k = first + 1; k last; ++k ) Type tmp = arrayk; for ( int j = k; k first; j ) if ( arrayj 1 tmp ) arrayj = arrayj 1; else arrayj = tmp; goto finished; arrayfirst = tmp; finished: ; Merge sort 28 8.5.4 Example Consider the following is of unsorted array of 25 entries 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 77 49 35 61 48 73 23 95 3 89 37 57 99 17 32 94 28 15 55 7 51 88 97 62 We will call insertion sort if the list being sorted of size N = 6 or lessMerge sort 29 8.5.4 Example We call mergesort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 77 49 35 61 48 73 23 95 3 89 37 57 99 17 32 94 28 15 55 7 51 88 97 62 mergesort( array, 0, 25 ) Merge sort 30 8.5.4 Example We are calling mergesort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 77 49 35 61 48 73 23 95 3 89 37 57 99 17 32 94 28 15 55 7 51 88 97 62 First, 25 – 0 6, so find the midpoint and call mergesort recursively midpoint = (0 + 25)/2; // == 12 mergesort( array, 0, 12 ); mergesort( array, 0, 25 ) Merge sort 31 8.5.4 Example We are now executing mergesort( array, 0, 12 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 77 49 35 61 48 73 23 95 3 89 37 57 99 17 32 94 28 15 55 7 51 88 97 62 First, 12 – 0 6, so find the midpoint and call mergesort recursively midpoint = (0 + 12)/2; // == 6 mergesort( array, 0, 6 ); mergesort( array, 0, 12 ) mergesort( array, 0, 25 ) Merge sort 32 8.5.4 Example We are now executing mergesort( array, 0, 6 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 77 49 35 61 48 73 23 95 3 89 37 57 99 17 32 94 28 15 55 7 51 88 97 62 Now, 6 – 0 ≤ 6, so find we call insertion sort mergesort( array, 0, 6 ) mergesort( array, 0, 12 ) mergesort( array, 0, 25 ) Merge sort 33 8.5.4 Example Insertion sort just sorts the entries from 0 to 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 77 49 35 61 48 73 23 95 3 89 37 57 99 17 32 94 28 15 55 7 51 88 97 62 insertionsort( array, 0, 6 ) mergesort( array, 0, 6 ) mergesort( array, 0, 12 ) mergesort( array, 0, 25 ) Merge sort 34 8.5.4 Example Insertion sort just sorts the entries from 0 to 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 35 48 49 61 77 73 23 95 3 89 37 57 99 17 32 94 28 15 55 7 51 88 97 62 – This function call completes and so we exit insertionsort( array, 0, 6 ) mergesort( array, 0, 6 ) mergesort( array, 0, 12 ) mergesort( array, 0, 25 ) Merge sort 35 8.5.4 Example This call to mergesort is now also finished, so it, too, exits 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 35 48 49 61 77 73 23 95 3 89 37 57 99 17 32 94 28 15 55 7 51 88 97 62 mergesort( array, 0, 6 ) mergesort( array, 0, 12 ) mergesort( array, 0, 25 ) Merge sort 36 8.5.4 Example We return to continue executing mergesort( array, 0, 12 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 35 48 49 61 77 73 23 95 3 89 37 57 99 17 32 94 28 15 55 7 51 88 97 62 We continue calling midpoint = (0 + 12)/2; // == 6 mergesort( array, 0, 6 ); mergesort( array, 6, 12 ); mergesort( array, 0, 12 ) mergesort( array, 0, 25 ) Merge sort 37 8.5.4 Example We are now executing mergesort( array, 6, 12 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 35 48 49 61 77 73 23 95 3 89 37 57 99 17 32 94 28 15 55 7 51 88 97 62 Now, 12 – 6 ≤ 6, so find we call insertion sort mergesort( array, 6, 12 ) mergesort( array, 0, 12 ) mergesort( array, 0, 25 ) Merge sort 38 8.5.4 Example Insertion sort just sorts the entries from 6 to 11 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 35 48 49 61 77 73 23 95 3 89 37 57 99 17 32 94 28 15 55 7 51 88 97 62 insertionsort( array, 6, 12 ) mergesort( array, 6, 12 ) mergesort( array, 0, 12 ) mergesort( array, 0, 25 ) Merge sort 39 8.5.4 Example Insertion sort just sorts the entries from 6 to 11 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 35 48 49 61 77 3 23 37 73 89 95 57 99 17 32 94 28 15 55 7 51 88 97 62 – This function call completes and so we exit insertionsort( array, 6, 12 ) mergesort( array, 6, 12 ) mergesort( array, 0, 12 ) mergesort( array, 0, 25 ) Merge sort 40 8.5.4 Example This call to mergesort is now also finished, so it, too, exits 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 35 48 49 61 77 3 23 37 73 89 95 57 99 17 32 94 28 15 55 7 51 88 97 62 mergesort( array, 6, 12 ) mergesort( array, 0, 12 ) mergesort( array, 0, 25 ) Merge sort 41 8.5.4 Example We return to continue executing mergesort( array, 0, 12 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 35 48 49 61 77 3 23 37 73 89 95 57 99 17 32 94 28 15 55 7 51 88 97 62 We continue calling midpoint = (0 + 12)/2; // == 6 mergesort( array, 0, 6 ); mergesort( array, 6, 12 ); merge( array, 0, 6, 12 ); mergesort( array, 0, 12 ) mergesort( array, 0, 25 ) Merge sort 42 8.5.4 Example We are executing merge( array, 0, 6, 12 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 35 48 49 61 77 3 23 37 73 89 95 57 99 17 32 94 28 15 55 7 51 88 97 62 These two subarrays are merged together merge( array, 0, 6, 12 ) mergesort( array, 0, 12 ) mergesort( array, 0, 25 ) Merge sort 43 8.5.4 Example We are executing merge( array, 0, 6, 12 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 57 99 17 32 94 28 15 55 7 51 88 97 62 These two subarrays are merged together – This function call exists merge( array, 0, 6, 12 ) mergesort( array, 0, 12 ) mergesort( array, 0, 25 ) Merge sort 44 8.5.4 Example We return to executing mergesort( array, 0, 12 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 57 99 17 32 94 28 15 55 7 51 88 97 62 We are finished calling this function as well midpoint = (0 + 12)/2; // == 6 mergesort( array, 0, 6 ); mergesort( array, 6, 12 ); merge( array, 0, 6, 12 ); Consequently, we exit mergesort( array, 0, 12 ) mergesort( array, 0, 25 ) Merge sort 45 8.5.4 Example We return to executing mergesort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 57 99 17 32 94 28 15 55 7 51 88 97 62 We continue calling midpoint = (0 + 25)/2; // == 12 mergesort( array, 0, 12 ); mergesort( array, 12, 25 ); mergesort( array, 0, 25 ) Merge sort 46 8.5.4 Example We are now executing mergesort( array, 12, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 57 99 17 32 94 28 15 55 7 51 88 97 62 First, 25 – 12 6, so find the midpoint and call mergesort recursively midpoint = (12 + 25)/2; // == 18 mergesort( array, 12, 18 ); mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 47 8.5.4 Example We are now executing mergesort( array, 12, 18 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 57 99 17 32 94 28 15 55 7 51 88 97 62 Now, 18 – 12 ≤ 6, so find we call insertion sort mergesort( array, 12, 18 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 48 8.5.4 Example Insertion sort just sorts the entries from 12 to 17 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 57 99 17 32 94 28 15 55 7 51 88 97 62 insertionsort( array, 12, 18 ) mergesort( array, 12, 18 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 49 8.5.4 Example Insertion sort just sorts the entries from 12 to 17 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 17 28 32 57 94 99 15 55 7 51 88 97 62 – This function call completes and so we exit insertionsort( array, 12, 18 ) mergesort( array, 12, 18 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 50 8.5.4 Example This call to mergesort is now also finished, so it, too, exits 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 17 28 32 57 94 99 15 55 7 51 88 97 62 mergesort( array, 12, 18 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 51 8.5.4 Example We return to continue executing mergesort( array, 12, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 17 28 32 57 94 99 15 55 7 51 88 97 62 We continue calling midpoint = (12 + 25)/2; // == 18 mergesort( array, 12, 18 ); mergesort( array, 18, 25 ); mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 52 8.5.4 Example We are now executing mergesort( array, 18, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 17 28 32 57 94 99 15 55 7 51 88 97 62 First, 25 – 18 6, so find the midpoint and call mergesort recursively midpoint = (18 + 25)/2; // == 21 mergesort( array, 18, 21 ); mergesort( array, 18, 25 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 53 8.5.4 Example We are now executing mergesort( array, 18, 21 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 17 28 32 57 94 99 15 55 7 51 88 97 62 Now, 21 – 18 ≤ 6, so find we call insertion sort mergesort( array, 18, 21 ) mergesort( array, 18, 25 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 54 8.5.4 Example Insertion sort just sorts the entries from 18 to 20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 17 28 32 57 94 99 15 55 7 51 88 97 62 insertionsort( array, 18, 21 ) mergesort( array, 18, 21 ) mergesort( array, 18, 25 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 55 8.5.4 Example Insertion sort just sorts the entries from 18 to 20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 17 28 32 57 94 99 7 15 55 51 88 97 62 – This function call completes and so we exit insertionsort( array, 18, 21 ) mergesort( array, 18, 21 ) mergesort( array, 18, 25 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 56 8.5.4 Example This call to mergesort is now also finished, so it, too, exits 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 17 28 32 57 94 99 7 15 55 51 88 97 62 mergesort( array, 18, 21 ) mergesort( array, 18, 25 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 57 8.5.4 Example We return to executing mergesort( array, 18, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 17 28 32 57 94 99 7 15 55 51 88 97 62 We continue calling midpoint = (18 + 25)/2; // == 21 mergesort( array, 18, 21 ); mergesort( array, 21, 25 ); mergesort( array, 18, 25 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 58 8.5.4 Example We are now executing mergesort( array, 21, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 17 28 32 57 94 99 7 15 55 51 88 97 62 Now, 25 – 21 ≤ 6, so find we call insertion sort mergesort( array, 21, 25 ) mergesort( array, 18, 25 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 59 8.5.4 Example Insertion sort just sorts the entries from 21 to 24 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 17 28 32 57 94 99 7 15 55 51 88 97 62 insertionsort( array, 21, 25 ) mergesort( array, 21, 25 ) mergesort( array, 18, 25 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 60 8.5.4 Example Insertion sort just sorts the entries from 21 to 24 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 17 28 32 57 94 99 7 15 55 51 62 88 97 – This function call completes and so we exit insertionsort( array, 21, 25 ) mergesort( array, 21, 25 ) mergesort( array, 18, 25 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 61 8.5.4 Example This call to mergesort is now also finished, so it, too, exits 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 17 28 32 57 94 99 7 15 55 51 62 88 97 mergesort( array, 21, 25 ) mergesort( array, 18, 25 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 62 8.5.4 Example We return to continue executing mergesort( array, 18, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 17 28 32 57 94 99 7 15 55 51 62 88 97 We continue calling midpoint = (18 + 25)/2; // == 21 mergesort( array, 18, 21 ); mergesort( array, 21, 25 ); merge( array, 18, 21, 25 ); mergesort( array, 18, 25 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 63 8.5.4 Example We are executing merge( array, 18, 21, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 17 28 32 57 94 99 7 15 55 51 62 88 97 These two subarrays are merged together merge( array, 18, 21, 25 ) mergesort( array, 18, 25 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 64 8.5.4 Example We are executing merge( array, 18, 21, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 17 28 32 57 94 99 7 15 51 55 62 88 97 These two subarrays are merged together – This function call exists merge( array, 18, 21, 25 ) mergesort( array, 18, 25 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 65 8.5.4 Example We return to executing mergesort( array, 18, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 17 28 32 57 94 99 7 15 51 55 62 88 97 We are finished calling this function as well midpoint = (18 + 25)/2; // == 21 mergesort( array, 18, 21 ); mergesort( array, 21, 25 ); merge( array, 18, 21, 25 ); Consequently, we exit mergesort( array, 18, 25 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 66 8.5.4 Example We return to continue executing mergesort( array, 12, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 17 28 32 57 94 99 7 15 51 55 62 88 97 We continue calling midpoint = (12 + 25)/2; // == 18 mergesort( array, 12, 18 ); mergesort( array, 18, 25 ); merge( array, 12, 18, 25 ); mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 67 8.5.4 Example We are executing merge( array, 12, 18, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 17 28 32 57 94 99 7 15 51 55 62 88 97 These two subarrays are merged together merge( array, 12, 18, 25 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 68 8.5.4 Example We are executing merge( array, 12, 18, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 7 15 17 28 32 51 55 57 62 88 94 97 99 These two subarrays are merged together – This function call exists merge( array, 12, 18, 25 ) mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 69 8.5.4 Example We return to executing mergesort( array, 12, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 7 15 17 28 32 51 55 57 62 88 94 97 99 We are finished calling this function as well midpoint = (12 + 25)/2; // == 18 mergesort( array, 12, 18 ); mergesort( array, 18, 25 ); merge( array, 12, 18, 25 ); Consequently, we exit mergesort( array, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 70 8.5.4 Example We return to continue executing mergesort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 7 15 17 28 32 51 55 57 62 88 94 97 99 We continue calling midpoint = (0 + 25)/2; // == 12 mergesort( array, 0, 12 ); mergesort( array, 12, 25 ); merge( array, 0, 12, 25 ); mergesort( array, 0, 25 ) Merge sort 71 8.5.4 Example We are executing merge( array, 0, 12, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 13 23 35 37 48 49 61 73 77 89 95 7 15 17 28 32 51 55 57 62 88 94 97 99 These two subarrays are merged together merge( array, 0, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 72 8.5.4 Example We are executing merge( array, 0, 12, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 73 77 88 89 94 95 97 99 These two subarrays are merged together – This function call exists merge( array, 0, 12, 25 ) mergesort( array, 0, 25 ) Merge sort 73 8.5.4 Example We return to executing mergesort( array, 0, 25 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 73 77 88 89 94 95 97 99 We are finished calling this function as well midpoint = (0 + 25)/2; // == 12 mergesort( array, 0, 12 ); mergesort( array, 12, 25 ); merge( array, 0, 12, 25 ); Consequently, we exit mergesort( array, 0, 25 ) Merge sort 74 8.5.4 Example The array is now sorted 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 7 13 15 17 23 28 32 35 37 48 49 51 55 57 61 62 73 77 88 89 94 95 97 99 – Question: What is the runtime of this algorithmMerge sort 75 8.5.5 Runtime Analysis of Merge Sort Thus, the time required to sort an array of size n 1 is: – the time required to sort the first half, – the time required to sort the second half, and – the time required to merge the two lists Θ(1) n 1  That is: T(n)  n 2TΘ(n) n 1  2Merge sort 76 8.5.5 Runtime Analysis of Merge Sort Again, calling Maple, we have that this recurrence relation has the solution: rsolve( T(n) = 2T(n/2) + n, T(1) = 1, T(n) ); nn ln 2 ln   ln 2  Simplifying this, we have n + n lg(n) – The run time is Q(n ln(n)) – Later we will see the master theorem when we consider divideandconquer algorithms in generalMerge sort 77 8.5.5 Runtime Summary The following table summarizes the runtimes of merge sort Run Time Case Comments WorstQ(n ln(n)) No worst case AverageQ(n ln(n)) BestQ(n ln(n)) No best caseMerge sort 78 2 8.5.6 Why is it not O(n ) When we are merging, we are comparing values 2 – What operation prevents us from performing O(n ) comparisons – During the merging process, if 2 came from the second half, it was only compared to 3 and it was not compared to any other of the other n – 1 entries in the first array – In this case, we remove n inversions with one comparisonMerge sort 79 8.5.5 Comments In practice, merge sort is faster than heap sort, though they both have the same asymptotic run times Merge sort requires an additional array – Heap sort does not require Next we see quick sort – Faster, on average, than either heap or quick sort – Requires o(n) additional memoryMerge sort 80 Merge Sort The (likely) first implementation of merge sort was on the ENIAC in 1945 by John von Neumann – The creator of the von Neumann architecture used by all modern computers: http://en.wikipedia.org/wiki/VonNeumannMerge sort 81 Summary This topic covered merge sort: – Divide an unsorted list into two equal or nearly equal sub lists, – Sorts each of the sub lists by calling itself recursively, and then – Merges the two sub lists together to form a sorted listMerge sort 82 References Wikipedia, http://en.wikipedia.org/wiki/Sortingalgorithm http://en.wikipedia.org/wiki/SortingalgorithmInefficient.2Fhumoroussorts 1 Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, nd 2 Ed., Addison Wesley, 1998, §5.1, 2, 3. 2 Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw Hill, 1990, p.1379 and §9.1. rd 3 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, §7.1, p.2612. 4 Gruber, Holzer, and Ruepp, Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms, 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007. These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
Website URL
Comment
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017