MergeSort The desirable features of Mergesort It performs in O n log n in the worst case Selection Sort was O n2 Bubble Sort was also O n2 It is stable It is quite independent of the way the initial list is organized Drawbacks It may require an array of up to the size of the original list This can be avoided but the algorithms becomes significantly more complicated making it not worth while Instead of making it complicated we can use heapsort which is also O n log n 1 MergeSort Algorithm mergesort Item aux MAXN void mergesort Item a int left int right int mid right left 2 if right left return mergesort a left mid mergesort a mid 1 right merge a left mid right 2 MergeSort Algorithm mergeAB Item c Item a int N Item b int M int i j k for i 0 j 0 k 0 k N M k if i N c k b j continue if j M c k a i continue c k less a i b j a i b j 3 Mergesort Illustration 85 24 63 45 17 31 96 50 Mergesort Illustration 85 24 63 45 17 31 96 50 Mergesort Illustration 17 85 24 63 45 31 96 50 Mergesort Illustration 17 63 85 24 45 31 96 50 Mergesort Illustration 17 63 85 24 45 31 96 50 Mergesort Illustration 17 24 85 63 45 31 96 50 Mergesort Illustration 17 24 85 63 45 31 96 50 Mergesort Illustration 17 24 85 63 45 31 96 50 Mergesort Illustration 17 24 85 63 45 31 96 50 Mergesort Illustration 17 24 85 63 45 31 96 50 Mergesort Illustration 17 24 85 63 45 31 96 50 Mergesort Illustration 17 24 85 63 45 31 96 50 Mergesort Illustration 17 24 85 45 63 31 96 50 Mergesort Illustration 17 24 85 45 63 31 96 50 Mergesort Illustration 17 24 85 45 63 31 96 50 Mergesort Illustration 17 24 85 45 63 31 96 50 Mergesort Illustration 17 24 85 45 63 31 96 50 Mergesort Illustration 17 24 85 45 63 31 96 50 Mergesort Illustration 24 17 85 45 63 31 96 50 Mergesort Illustration 24 17 85 45 63 31 96 50 Mergesort Illustration 24 45 85 17 63 31 96 50 Mergesort Illustration 24 45 85 17 63 31 96 50 Mergesort Illustration 24 45 85 63 17 31 96 50 Mergesort Illustration 24 45 85 63 17 31 96 50 Mergesort Illustration 24 45 63 85 17 31 96 50 Mergesort Illustration 24 45 63 85 17 31 96 50 Mergesort Illustration 24 45 63 85 17 31 96 50 Mergesort Illustration 24 45 63 85 17 31 96 50 Mergesort Illustration 24 45 63 85 96 17 31 50 Mergesort Illustration 24 45 63 85 96 17 31 50 Mergesort Illustration 24 45 63 85 17 96 31 50 Mergesort Illustration 24 45 63 85 17 96 31 50 Mergesort Illustration 24 45 63 85 17 31 96 50 Mergesort Illustration 24 45 63 85 17 31 96 50 Mergesort Illustration 24 45 63 85 17 31 96 50 Mergesort Illustration 24 45 63 85 17 31 96 50 Mergesort Illustration 24 45 63 85 17 31 96 50 Mergesort Illustration 24 45 63 85 17 31 50 96 Mergesort Illustration 24 45 63 85 17 31 50 96 Mergesort Illustration 24 45 63 85 17 31 50 96 Mergesort Illustration 24 45 63 85 17 31 50 96 Mergesort Illustration 24 45 63 85 17 31 50 96 Mergesort Illustration 24 45 63 85 17 31 50 96 Mergesort Illustration 24 45 63 85 17 31 50 96 Mergesort Illustration 24 45 63 85 17 31 50 96 Mergesort Illustration 24 45 63 85 17 31 50 96 Mergesort Illustration 24 45 63 85 17 31 50 96 Mergesort Illustration 24 45 63 85 17 31 50 96 Mergesort Illustration 24 45 63 85 17 31 50 96 Mergesort Illustration 24 45 63 85 17 31 50 96 Mergesort Illustration 24 45 63 85 17 31 50 96 Mergesort Illustration 17 24 45 63 85 31 50 96 Mergesort Illustration 17 24 45 63 85 31 50 96 Mergesort Illustration 17 24 45 63 85 31 50 96 Mergesort Illustration 17 24 45 63 85 31 50 96 Mergesort Illustration 17 24 45 31 63 85 50 96 Mergesort Illustration 17 24 45 31 63 85 50 96 Mergesort Illustration 17 24 31 63 45 85 50 96 Mergesort Illustration 17 24 31 63 45 85 50 96 Mergesort Illustration 17 24 31 63 45 85 50 96 Mergesort Illustration 17 24 31 63 45 85 50 96 Mergesort Illustration 17 24 31 45 85 50 63 96 Mergesort Illustration 17 24 31 45 85 50 63 96 Mergesort Illustration 17 24 31 45 50 63 85 96 Mergesort Illustration 17 24 31 45 50 63 85 96 Mergesort Illustration 17 24 31 45 50 63 85 96 Mergesort Illustration 17 24 31 45 50 63 85 96 Mergesort Illustration 17 24 31 45 50 63 85 96 Mergesort Time complexity Best worst average case Each merge operation takes 0 k time for 2 lists each k 2 elements long merged into one list k elements long There will be log2n levels 1st level 2 n 2 long lists to be merged into 1 n long list 2nd level 4 n 4 long lists to be merged into 2 n 2 long lists 3rd level 8 n 8 long lists to be merged into 4 n 4 long lists Time Complexity O nlog2n Complexity of MergeSort k log n 73 Pass Number Number of merges Merge list length of comps moves per merge 1 2k 1 or n 2 1 or n 2k 21 2 2k 2 or n 4 2 or n 2k 1 22 3 2k 3 or n 8 4 or n 2k 2 23 k 1 21 or n 2k 1 2k 2 or n 4 2k 1 k 20 or n 2k 2k 1 or n 2 2k Complexity of MergeSort Multiplying the number of merges by the maximum number of comparisons per merge we get 2k 1 21 2k k passes each require k 2 2 k 2 2 2 k 2 comparisons and moves But k lg n and hence we get lg n n comparisons 21 2k 1 2k or O n lgn 20 2k 2k 74 Stable vs Non Stable Sorts We frequently use sorting methods for items with multiple keys Sometimes we need to apply the sorting with different keys For instance we want to sort a list of people based on first name and than on age So Black age 30 should appear before Jones age 30 If we sort a list based on the first key name and then apply a sort based on the second key age how can we guarantee that the list is still ordered based on the first key Definition A sorting method is said the be stable if it preserves the relative order of the items …
View Full Document
Unlocking...