Divide and Conquer Merge Sort

As discussed above, one technique that often works for developing efficient algorithms is the divide-and-conquer approach. Suppose a friend and I were working together trying to put our deck of cards in order. We could divide the problem up by splitting the deck of cards in half with one of us sorting each of the halves. Then we just need to figure out a way of combining the two sorted stacks.

The process of combining two sorted lists into a single sorted result is called merging. If you think about it, merging is pretty simple. Since our two stacks are sorted, each has its smallest value on top. Whichever of the top values is the smallest will be the first item in the merged list. Once the smaller value is removed, we can look at the tops of the stacks again, and whichever top card is smaller will be the next item in the list. We just continue this process of placing the smaller of the two top values into the big list until one of the stacks runs out. At that point, we finish out the list with the cards from the remaining stack.

Here is a Python implementation of the merge process. In this code, lst1 and lst2 are the smaller lists and lst3 is the larger list where the results are placed. In order for the merging process to work, the length of lst3 must be equal to the sum of the lengths of lst1 and lst2. You should be able to follow this code by studying the accompanying comments:

def merge(lst1, lst2, lst3):

# merge sorted lists lst1 and lst2 into lst3

# these indexes keep track of current position in each list i1, i2, i3 = 0, 0, 0 # all start at the front n1, n2 = len(lst1), len(lst2)

# Loop while both lst1 and lst2 have more items while i1 < n1 and i2 < n2:

if lst1[i1] < lst2[i2]: # top of lst1 is smaller lst3[i3] = lst1[i1] # copy it into current spot in lst3 i1 = i1 + 1

else: # top of lst2 is smaller lst3[i3] = lst2[i2] # copy it into current spot in lst3 i2 = i2 + 1

# Here either lst1 or lst2 is done. One of the following loops will

# execute to finish up the merge.

# Copy remaining items (if any) from lst1 while i1 < n1:

# Copy remaining items (if any) from lst2 while i2 < n2:

With this merging algorithm in hand, it's easy to see the general structure for a divide-and-conquer sorting algorithm.

Algorithm: mergeSort nums split nums into two halves sort the first half sort the second half merge the two sorted halves back into nums

Looking at the steps in this algorithm, the first and last parts look easy. We can use slicing to split the list, and we can use the merge function that we just wrote to put the pieces back together. But how do we sort the two halves?

Well, let's think about it. We are trying to sort a list, and our algorithm requires us to sort two smaller lists. This sounds like a perfect place to use recursion. Maybe we can use mergeSort itself to sort the two lists. Let's go back to our recursion guidelines and see if we can develop a proper recursive algorithm.

In order for recursion to work, we need to find at least one base case that does not require a recursive call, and we also have to make sure that recursive calls are always made on smaller versions of the original problem. The recursion in our mergeSort will always occur on a list that is half as large as the original, so the latter property is automatically met. Eventually, our lists will be very small, containing only a single item. Fortunately, a list with just one item is already sorted! Voila, we have a base case. When the length of the list is less than 2, we do nothing, leaving the list unchanged.

Given our analysis, we can update the mergeSort algorithm to make it properly recursive.

split nums into two halves mergeSort the first half mergeSort the second half merge the two sorted halves back into nums We can translate this algorithm directly into Python code.

def mergeSort(nums):

# Put items of nums in ascending order n = len(nums)

# Do nothing if nums contains 0 or 1 items if n > 1:

# recursively sort each piece mergeSort(nums1) mergeSort(nums2)

# merge the sorted pieces back into original list merge(nums1, nums2, nums)

I know this use of recursion may still seem a bit mysterious to you. You might try tracing this algorithm with a small list (say eight elements), just to convince yourself that it really works. In general, though, tracing through recursive algorithms can be tedious and often not very enlightening.

Recursion is closely related to mathematical induction, and it requires something of a leap of faith before it becomes comfortable. As long as you follow the rules and make sure that every recursive chain of calls eventually reaches a base case, your algorithms will work. You just have to trust and let go of the grungy details. Let Python worry about that for you!

+1 0

Post a comment