• Author / Uploaded
• Arnex Fesariton

Citation preview

Merge Sort Algorithm Conceptually, a merge sort works as follows Merge Sort – Divide & Conquer •Divide: Divide the n-element sequence to be sorted into two subsequences of n/2 elements each. •Conquer: Sort the two subsequences recursively (I.e. by using merge sort again on the subsequences). •Combine: Merge the two sorted subsequences to produce the sorted answer. • This procedure will bottom out when the list to be sorted is of length 1 so we must take this into account in our algorithm design. Merge sort incorporates two main ideas to improve its runtime: 1. A small list will take fewer steps to sort than a large list. 2. Fewer steps are required to construct a sorted list from two sorted lists than two unsorted lists. For example, you only have to traverse each list once if they're already sorted. Advantages: Many useful algorithms are recursive • These algorithms employ a divide and conquer approach. • Think of merging two lists of sorted numbers. • All that is needed is to look at the top items and add the appropriate one each time • The merge sort algorithm closely follows the Divide and Conquer paradigm. It operates as follows, Merge Sort – Visual Example 75 55 15 20 85 30 35 10 60 40 50 25 45 80 70 65 • Divide list into 2 sublist, so at next level of recursion we have : 75 55 15 20 85 30 35 10 Sub-list 1 60 40 50 25 45 80 70 65 Sub-list 2 • We keep splitting our sublists into smaller sublists until we can’t split any further • Eventually we will end up with distinct pairs of already sorted sublists which need to be merged together. 75 55 15 20 85 30 35 10 60 40 50 25

70

65

75 55 85 30 35 10 60 40 50 25 45 80 70 65 Merge Sort – Visual Example (2) • After the first merge we end up with half as many sublists as before the merge : 55 75 15 20 30 85 10 35 40 60 25 50 45 80 65 70 • We again merge the susequent sorted sublists together again, thus reducing the number of sublists again to half : 15 20 55 75 10 30 35 85 25 40 50 60 45 65 70 80 • Repeating the same procedure again we end up with 2 sorted sublists to be merged : 10 15 20 30 35 55 75 85 25 40 45 50 60 65 70 80 • Merging these two sorted sublist together we end up with our original listed sorted! : 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 Merge Sort – Pseudo Code MergeSort(List[], leftIndex, rightIndex) Begin: if leftIndex < rightIndex then mid = (leftIndex + rightIndex) / 2 MergeSort(List[], leftIndex, mid) // split left sublist MergeSort(List[], mid + 1, rightIndex) // split right sublist Merge(List[], leftIndex, mid, rightIndex) // merge sorted sublists endif End Stable Sort • The prime disadvantage of mergesort is that extra space proportional toN is needed in a straightforward implementation. •Definition: A sorting method is said to be “stable” if it

preserves the relative order of duplicate keys in the file • If we have an alphabetised list of students and their year of graduation is sorted by year, a stable method produces a list in which people in the same class are still in alphabetical order, but a non-stable method is likely to produce a list with no vestige of the original alphabetic order. Merging • Given two ordered input files, we can combine them into one ordered output file simply by keeping track of the smallest element in each file and entering a loop where the smaller of the two elements is moved to the output. • If merge sort is implemented using a “stable merge”, then the result of the sort is stable. • Method of merging to be presented is “Abstract in-place merge” • Thisa lg o r it h m merges by copying the second array into an arraya ux (auxiliary array), in reverse order back to back with the first. • It is a stable merge procedure.