When you are faced with a huge task, what do you usually do? Well, if you’re a little bit like me, then you split it into smaller chunks, complete them individually and later combine into a bigger one. This exact approach is used by Merge Sort. Following article will cover its implementation with detailed explanation, including a study of dreadful (not really) recursion. Ready?

Overview

Divide and Conquer is a technique used in programming to solve a problem by dividing it into sub-problems, which are much quicker to solve. Splitting is done via recursion, hence this part tends to be more problematic - we’ll address that difficulty in understanding in the simplest way possible. Merge Sort uses Divide and Conquer to break a big list into smaller ones (they are easier to sort) and later combine them all together into one sorted output.

Problem

Sort a list of elements.

Steps

1. Given list_to_sort, if it is empty or has only one element, then return it. Lists with size 0 or 1 are super easy to sort - basically, they are already sorted :).
2. If list_to_sort has more than one element, then calculate its middle index and based on that value split it into left half and right half. For each of them go to step 1 and treat it as list_to_sort (this is recursion). You will do this until you divide one of these sub-lists so deep, that it is empty or has only one element.
3. Every time recursion ends and you end up with calculated left_list and right_list (see implementation in Python), then combine them by iterating over each element, comparing it and placing in the correct position. This step is solving a sub-problem - sorting a smaller list - only to gradually combine it into one big sorted solution.

Visualization

Pictures below pretty much speak for themselves. I just want to draw your attention to two things. The first is recursion level - we are dividing the list recursively into smaller and smaller chunks (the half of the half of the half...). Imagine Leonardo DiCaprio in “Inception” going into next dream within a dream. He would love to have each dream labeled to know how to come back. This is why on the left we keep track of the order of each “Inception” level. The second important thing is the way we split list_to_sort. It’s always done using calculated middle_of_list. We go as deep as possible to find the smallest left sub-list, then right sub-list and later we come back upwards with the help of aforementioned recursion levels map on the left.

Merge sort implementation in Python

In the previous paragraph recursion levels were labeled using a colorful star. In code I needed to deploy a bit less fun solution - ids. Take a closer look at the output, that below implementation produces. Print statements scattered around it should give you a better understanding of what’s going on. Do you see similarities to the visualization you studied earlier?

import random

# This is only for presentation purposes.
random.seed(30)


# Every time recursion ends and you end up with calculated left_list and right_list, then combine them by iterating
# over each element, comparing it and placing in the correct position. This function is solving a sub-problem -
# sorting a smaller list and returning it.
def merge_lists(left_list, right_list):
    print(f"I'm function merge_lists. This is my input: left_list = {left_list}, right_list = {right_list}")
    result = []
    left_index, right_index = 0, 0

    # Sorting happens here.
    while left_index < len(left_list) and right_index < len(right_list):
        if left_list[left_index] < right_list[right_index]:
            result.append(left_list[left_index])
            left_index += 1
        else:
            result.append(right_list[right_index])
            right_index += 1

    # Let's append to result all that is left after "while" loop comparisons.
    result += left_list[left_index:]
    result += right_list[right_index:]

    print(f"I'm function merge_lists. This is what I did with input: {result}")
    return result


# This is actual function that you call to sort a list.
def merge_sort(list_to_sort):
    # This is only for presentation purposes.
    recursion_level_id = generate_random_unique_id()

    # Given list_to_sort, if it is empty or has only one element, then return it. Lists with size 0 or 1 are super
    # easy to sort - basically, they are already sorted :).
    if len(list_to_sort) <= 1:
        return list_to_sort

    # If list_to_sort has more than one element, then calculate its middle index and based on that value split it
    # into left half and right half.
    middle_of_list = len(list_to_sort) // 2

    # This is recursion. A function merge_sort calls itself with first and second half of the input list. It will do
    # this until it reaches the condition from the "if" statement above. Only then it returns.
    left_list = merge_sort(list_to_sort[:middle_of_list])
    print(f"I'm function merge_sort. left_list value on recursion level with id {recursion_level_id} is {left_list}")
    right_list = merge_sort(list_to_sort[middle_of_list:])
    print(f"I'm function merge_sort. right_list value on recursion level with id {recursion_level_id} is {right_list}")

    # merge_lists solves a sub-problem by sorting a smaller list (combining two small lists).
    return merge_lists(left_list, right_list)


def generate_random_unique_id():
    return "md" + str(random.randint(100, 1000))


print(f"Result: {merge_sort(list_to_sort=[52, 21, 10, 33, 68, 49])}")

Output of merge sort:

I'm function merge_sort. left_list value on recursion level with id md927 is [52]
I'm function merge_sort. left_list value on recursion level with id md725 is [21]
I'm function merge_sort. right_list value on recursion level with id md725 is [10]
I'm function merge_lists. This is my input: left_list = [21], right_list = [10]
I'm function merge_lists. This is what I did with input: [10, 21]
I'm function merge_sort. right_list value on recursion level with id md927 is [10, 21]
I'm function merge_lists. This is my input: left_list = [52], right_list = [10, 21]
I'm function merge_lists. This is what I did with input: [10, 21, 52]
I'm function merge_sort. left_list value on recursion level with id md652 is [10, 21, 52]
I'm function merge_sort. left_list value on recursion level with id md769 is [33]
I'm function merge_sort. left_list value on recursion level with id md315 is [68]
I'm function merge_sort. right_list value on recursion level with id md315 is [49]
I'm function merge_lists. This is my input: left_list = [68], right_list = [49]
I'm function merge_lists. This is what I did with input: [49, 68]
I'm function merge_sort. right_list value on recursion level with id md769 is [49, 68]
I'm function merge_lists. This is my input: left_list = [33], right_list = [49, 68]
I'm function merge_lists. This is what I did with input: [33, 49, 68]
I'm function merge_sort. right_list value on recursion level with id md652 is [33, 49, 68]
I'm function merge_lists. This is my input: left_list = [10, 21, 52], right_list = [33, 49, 68]
I'm function merge_lists. This is what I did with input: [10, 21, 33, 49, 52, 68]
Result: [10, 21, 33, 49, 52, 68]

Be sure to check other algorithms I explained on Coders Bible.