#_________________________ Merge Sort____________________________________ #3.py # This is similar to the Quicksort (next program), and is also an O(nlogn) algorithm. It is useful when the # list is very, very large (e.g., list of names) and is stored on disk, because it works by # creating sublists and doing a lot of "ordered copying" (or "merging"). # Let's do the example on page 449 of your text, to save some reading time. ''' node 0 nlist: 3 1 4 1 5 9 2 6 (eight numbers in the list) step1: split into "equal-sized" (roughly) sublists ''' # Now please pay attention to the order in which things are done. We are splitting recursively # and when we write code one statement comes after the other, dictating the order of execution. # Actually the call will be "MergeSort", but since we are really splitting lists into roughly # equal pieces, it will look like this: ''' 3,1,4,1,5,9,2,6 3,1,4,1 Split (the left split is working recursively) 3,1 Split(left split is still recursing) 3 1 Split (left split has bottomed; we have two sublists [3] and [1]) Now Merge is called to output and ordered sublist [1 3]. Merge is the last statement in the MergeSort. So Python then goes up one level in the recursion, after the merge. Where are we now? We had left off at 4,1 4,1 Split (right split off the left recurses) 4 1 Split (right split has bottomed; we have two sublists [4] and [1]) Merge is called again, and gives [ 1 4] as sorted sublist Where are we now? We have two sublists [1 , 3] and [1, 4] and the "Merge()" has to run after every pair of sublists is found Merge is called and gives [1, 1, 3, 4] Where are we now? We have finished recursing the left side, and now have to recurse the right side. We have only one sublist -- the left one. Recursing the right side will give the right sublist and then we can call Merge(). 5, 9, 2, 6 Split (recurse right) 5, 9 Split (left split off the right recurses) 5 9 bottoms Merge is called and gives sublist [5, 9] 2, 6 Split (right split off the right recurses) 2 6 bottoms Merge is called and gives sublist [2, 6] Where are we now? We have two sublists [5, 9] and [2, 6]. Whenever a pair of sublists is ready Merge() is called. It now gives [2, 5, 6, 9] We are back at the second level of the tree, just under the root node with two sublists: [1, 1, 3, 4] made earlier [2, 5, 6, 9] just made We have two sublists. Merge() is called, and outputs the final list. [1, 1, 2, 3, 4, 5, 6, 9] Note: you can trace this output below, via my print statments.''' # The only question really is this: given two sublists (see above), how do we # "merge" them so that the result list is sorted. Yes, each sublist is sorted to begin with. But # when we put them together to make a bigger list, how to ensure it is sorted? # Answer: by using an index for each of the two lists and copying the smaller of the numbers # pointed to by the indexes into the output list. # Note that the sublists may not be equal-sized. We need only roughly equal. #----------------- The merge() function merges two sorted lists; output is a sorted list ----------------- def iMerge(firstlist, secondlist, resultlist): # the iMerge function works iteratively # firstlist and secondlist are sorted; merge them and create a new list resultlist that # is also sorted. # Imagine my left index finger points to the start of the **first list** findex = 0 #Imagine my right index finger points to the start of the **second list** sindex = 0 # Imagine we use one of your fingers to point to the start of the **result list** which is now empty rindex = 0 # Now all we have to do is to copy the numbers from firstlist and secondlist into # resultlist, but in ascending (sorted) order # How far to copy? We need the limits flimit = len(firstlist) slimit = len(secondlist) while (findex < flimit) and (sindex < slimit): if (firstlist[findex] < secondlist[sindex]): # number in first list is smaller resultlist[rindex] = firstlist[findex] findex = findex + 1 rindex = rindex + 1 print(" copied from 1") else: # otherwise, number in second list is smaller resultlist[rindex] = secondlist[sindex] sindex = sindex + 1 rindex = rindex + 1 print("copied from 2") # When the above loop is done, we are here. It means one of the two lists has been # exhausted and there are (sorted) numbers left over in the other list. # So simply copy these numbers (they are sorted anyway) into the resultlist # Only one of the following two loops will run, to append the non-exhausted list to the result. while (findex < flimit) : # if we enter this loop, it means secondlist was exhausted resultlist[rindex] = firstlist[findex] findex = findex + 1 rindex = rindex + 1 while (sindex < slimit) : # if we enter this loop, it means firstlist was exhausted resultlist[rindex] = secondlist[sindex] sindex = sindex + 1 rindex = rindex + 1 # We are done. Both sorted lists were copied into resultlist in such a (simple) way that # resultlist is sorted. #------------- Now comes the recursive merge sort ------------------------------------------------- # This is a "divide and conquer strategy" just like quicksort. Both give you that tree structure. # If there are n elements in the list, it takes log n steps to build the tree. Since the work at each level # is not a constant, but related to n, we get an n log n algorithm, making mergesort an # O(n log n) algorithm. Just like Quicksort. def MergeSort(nlist): # sort nlist n = len(nlist) if (n > 1): # as long as there is sorting work (i.e., two or more numbers to be sorted) # so the base case of the recursion is when n == 1; this function simply # returns, doing nothing m = n // 2 # get a roughly equal split size for each sublist firstlist = nlist[ :m] # slicing goes from 0 ..... (m-1) secondlist = nlist[m: ] # slicing goes from m to (n-1) #Now the old recursion trick. MergeSort(firstlist) # recursively sort the first sublist MergeSort(secondlist) # recursively sort the second sublist # Now the firstsublist and second sublist have been sorted [really, all we did was to keep # spitting nlist repeatedly as we walked down the tree; in the end we arrive at the leaves # of the tree, as in the above example. Each of the final sublists has just one number. # The next step is to back up the recursion, going in the reverse order in which we came # down (we have to retrace all the function calls), merging sublists as we go up to # make the big resultlist which will be sorted. # So all of the sorting work is really doing by the "iMerge()" algorithm, just like the # "iSplit()" function did all the qork in QuickSort() iMerge(firstlist, secondlist, nlist) # sorted numbers get put back in (i.e., nlist # gets to be the resultlist) print(firstlist, secondlist) print(nlist) print(" ") def wait(): x = input(); def main(): nlist = [28, 12, 4, 19, 22, 7, 65, 87, 3, 99, 21, 32, 1, 83, 17, 79, 81, 33] print("Original list",nlist) print(" ") MergeSort(nlist) print("Sorted list",nlist) wait() nlist = [3, 1, 4, 1, 5, 9, 2, 6] print("Original list",nlist) print(" ") MergeSort(nlist) print("Sorted list",nlist) main()