Question? Leave a message!




Merge sort

Merge sort
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
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 © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Merge sort 2 Outline This topic covers merge sort – A recursive divide-and-conquer algorithm – Merging two lists – The merge sort algorithm – A run-time 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 sub-lists, • Sort each sub-list recursively using merge sort, and • Merge the two sorted sub-lists into a single sorted list This is the first significant divide-and-conquer algorithm we will see Question: How quickly can we recombine the two sub-lists into a single sorted list?Merge 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 straight-forward: – 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 in-place – 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 sub-lists – 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 category