Merge sort

Intuition

If you wonder how you might use recursion to sort an array, merge sort is a natural answer. In other words, if you wonder how you might enlist your friends to help you sort in a divide and conquer fashion, merge sort is a natural answer.

Merge

Suppose you want to sort a deck of cards, but you’re lazy, so you split the deck in half and give one half to one friend and another half to the another friend and get each friend to sort their half and then give the cards back to you.

You can then merge the two sorted halves as follows. Put the two halves next to each other.

Turn over the top card for each half and take whichever card is lower and start a new pile that will be for the sorted deck.

Do that again with the next top card on the half that had the lower card and the same top card on the half that had the higher card and take the card that is lower between those two cards and add it to the pile that you created.

Keep doing that until one of the halves runs out.

Add the cards from the remaining half to the pile for the sorted deck.

Recursion

We’ve described how you can get one sorted deck if given two sorted halves.

But this same logic applies to your two friends. Each of your friends could be lazy and find 2 other friends and split their deck in half and get their friends to sort half of their halves.

And the same logic applies to the friends of friends. Here’s a picture of that process (F = Friend, FoF = friend of friend):

		          You
		   /                 \  
    	  F1             	 F2
      /       \		    /        \
    FoF1.1   FoF1.1   FoF2.1    FoF1.1

This tree keeps growing until your friend of friend of friends… each only have 2 cards and they hand their friend of friend of friend of friends… 1 card each and that friend doesn’t even have to do anything, because their half is already sorted (it’s only 1 card). So the friend of friend of friends… immediately take back their 2 sorted halves of 1 card and follow the merging procedure to get a sorted deck of 2 cards and then the friend of friends take back their 2 sorted halves of 2 cards and follow the merging procedure to get a sorted deck of 4 cards and so on until your 2 friends hand you back their halves sorted.

def merge_sort(arr):
    if len(arr) == 1:
        return

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    merge_sort(left)
    merge_sort(right)

    i = j = k = 0
    # Remember this is testing the bounds of left and right not arr
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            arr[k] = left[i]
            i += 1
            k += 1
        else:
            arr[k] = right[j]
            j += 1
            k += 1

    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1

    while j < len(right):
        arr[k] = right[j]
        j += 1
        k += 1
        
def test_merge_sort():
    arr = [1, 5, 3, -4, -10, 0]
    merge_sort(arr)
    assert arr == [-10, -4, 0, 1, 3, 5], arr
    
test_merge_sort()