Merge Sort7:10 with Jay McGavren
Let's review another sorting algorithm, Merge Sort, so we can compare it with Quick Sort.
If you'd like more details on Merge Sort, check this stage from our Introduction to Data Structures course.
Both Quicksort and Merge Sort are recursive. The difference between them is in the sorting mechanism itself. Whereas Quicksort sorts a list into two sub-lists that are less than or greater than a pivot value, Merge Sort simply splits the list in half recursively, and then sorts the halves as it merges them back together. (That's why it's called "Merge Sort".)
# You may recognize this code at the top by now; it just loads a file full # of numbers into a list. import sys from load import load_numbers numbers = load_numbers(sys.argv) # Let's define a recursive merge sort function. As usual, it takes the # list or sub-list that we want it to sort. def merge_sort(values): # Our base case is the same as with Quicksort. If the list has zero or one # values, there's nothing to sort, so we return it as-is. if len(values) <= 1: return values # If we didn't return, it means we're in the recursive case. So first we need # to split the list in half. We need to know the index we should split on, # so we get the length of the list and divide it by 2. So for example if # there are 8 items in the list, we'll want an index of 4. But what if there # were an odd number of items in the list, like 7? We can't have an index of # 3.5, so we'll need to round down in that case. Since we're working in # Python currently, we can take advantage of a special Python operator that # divides and rounds the result down: the floor division operator. It # consists of a double slash. middle_index = len(values) // 2 # Now we'll use the Python slice syntax to get the left half of the list. # We'll pass that list to a recursive call to the merge_sort function. left_values = merge_sort(values[:middle_index]) # We'll also use slice syntax to get the right half of the list, and pass # that to merge_sort as well. right_values = merge_sort(values[middle_index:]) # Now we need to merge the two halves together, and sort them as we do it. # We'll create a list to hold the sorted values. sorted_values =  # Now we get to the complicated part - merging the two halves together and # sorting them as we do it. # We'll be moving from left to right through the left half of the list, # copying values over to the sorted_values list as we go. This left_index # variable will help us keep track of our position. left_index = 0 # At the same time, we'll also be moving from left to right through the right # half of the list and copying values over, so we need a separate # right_index variable to track that position as well. right_index = 0 # We'll keep looping until we've processed all of the values in both halves # of the list. while left_index < len(left_values) and right_index < len(right_values): # We're looking to copy over the lowest values first. So first we test # whether the current value on the left side is less than the value on the # right side. if left_values[left_index] < right_values[right_index]: # If the left side value is less, that's what we'll copy to the sorted # list. sorted_values.append(left_values[left_index]) # And then we'll move to the next value in the left half of the list. left_index += 1 # Otherwise, the current value from the right half must have been lower. else: # So we'll copy that value to the sorted list instead. sorted_values.append(right_values[right_index]) # And then we'll move to the next value in the right half of the list. right_index += 1 # At this point one of the two unsorted halves still has a value remaining, # and the other is empty. We won't waste time checking which is which. # We'll just copy the remainder of both lists over to the sorted list. # The one with a value left will add that value, and the empty one will add # nothing. sorted_values += left_values[left_index:] sorted_values += right_values[right_index:] # All the numbers from both halves should now be copied to the sorted list, # so we can return it. return sorted_values # Finally, we need to kick the whole process off. We'll call the merge_sort # function with the list of numbers we loaded, and print the result. print(merge_sort(numbers))
Save the above code to a file named
merge_sort.py, in the same directory as
load.py. Let's try this on our file with eight numbers.
python merge_sort.py numbers/8.txt
It prints out the sorted list.
[2, 3, 3, 4, 5, 6, 7, 9]
- But again, this seems pretty magical. Let's add some print statements to get some insight into what it's doing.
- First, we'll print the unsorted list so we can refer to it. We'll add a print statement right before we call the
merge_sortfunction for the first time.
- Then we'll add another print statement within the
merge_sortfunction, right after the recursive calls. This will show us the sorted left half and right half that it's returning. Again, don't worry about the fancy Python formatting string; it just keeps the values neatly aligned.
print("%15s %-15s" % (left_values, right_values))
- Let's try running this again.
python merge_sort.py numbers/8.txt [4, 6, 2, 3, 9, 7, 3, 5]     [4, 6] [2, 3]     [7, 9] [3, 5] [2, 3, 4, 6] [3, 5, 7, 9] [2, 3, 3, 4, 5, 6, 7, 9]
- What we're seeing are the values being returned from the recursive
merge_sortfunction calls, not the original calls to
merge_sort. So what you see here is after we reach the base case with a list that's only one item in length, and the recursive calls start returning.
- The original list gets split into two unsorted halves:
[4, 6, 2, 3], and
[9, 7, 3, 5].
- The first half gets split in half again:
[2, 3], and each of those halves is halved again into single-element lists:
- There's nothing to sort in the single-element lists, so they're returned from the
- Those single-element lists get merged into two sub-lists: the
[2, 3]sub-lists look the same after sorting as they did before sorting.
- But the order is shifted when those two sub-lists get merged back into a single list:
[2, 3, 4, 6].
- Then we recursively sort the right half of the list:
[9, 7, 3, 5].
- It gets split in half again:
- And each of those halves gets broken into single-element lists.
- There's nothing to sort there, so they're returned as-is:
- The first two are sorted as they're merged:
- The order of the second two is unchanged:
- All those elements are sorted as they're merged into the second half of the full list:
[3, 5, 7, 9].
- And then the two halves are sorted as they're merged back into the full list:
[2, 3, 3, 4, 5, 6, 7, 9]
You need to sign up for Treehouse in order to download course files.Sign up