(Re)Implement Merge Sort in Python Step-by-Step With Visual Diagrams

Merge sort is one of the most elegant sorting algorithms you’ll encounter. Based on the divide-and-conquer paradigm, it’s not only efficient (O(n log n) time complexity) but also stable and relatively simple to implement. Despite this, it’s often presented in a purely theoretical or abstract way. In this article, we’ll walk through merge sort step by step with annotated Python code and conceptual explanations that include pseudo-visual diagrams to help cement your understanding.

1. Understanding the Problem: What Is Merge Sort?

At its core, merge sort recursively breaks a list into smaller halves until the list is trivially sorted (a single element or empty list), and then merges those sorted sublists back into one in the correct order. Here’s the high-level idea:

Divide: Split the list into two halves.
Conquer: Recursively sort each half.
Combine: Merge the two sorted halves together.

This approach guarantees a consistent performance of O(n log n) regardless of input structure.

# Example input:
arr = [8, 3, 5, 4, 7, 6, 1, 2]
# Expected output:
# [1, 2, 3, 4, 5, 6, 7, 8]

2. The Recursive Breakdown: Divide Phase

Let’s start by implementing the recursive breakdown. For educational clarity, we will show debug prints in the function to make its step-by-step flow visible.

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

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

This is a textbook recursive pattern. Each level of division reduces the problem into smaller sub-problems until we’re left with arrays of a single element, which are trivially sorted.

Visualization:

[8, 3, 5, 4, 7, 6, 1, 2]
=> split => [[8, 3, 5, 4], [7, 6, 1, 2]]
=> split => [[[8, 3], [5, 4]], [[7, 6], [1, 2]]]
=> split => [[8], [3]], [[5], [4]], [[7], [6]], [[1], [2]]

3. The Merge Phase: Combining Sorted Arrays

Now let’s write the merge function responsible for combining two sorted subarrays into a single sorted array.

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # Append remaining elements
    result.extend(left[i:])
    result.extend(right[j:])

    return result

This function is key to merge sort's efficiency. We compare elements one-by-one from each left and right sublist, maintaining their sorted order, and then glue them back together. Each merge call runs in linear time O(n), and since we break the array into log(n) levels, the total time complexity becomes O(n log n).

4. Fully Working Example with Debug Output

Let's package everything into a single script with logging to dissect each phase of the recursion and merging process.

def merge_sort(arr, depth=0):
    indent = "  " * depth
    if len(arr) <= 1:
        print(f"{indent}Returning: {arr}")
        return arr

    mid = len(arr) // 2
    print(f"{indent}Splitting: {arr}")
    left = merge_sort(arr[:mid], depth + 1)
    right = merge_sort(arr[mid:], depth + 1)

    merged = merge(left, right)
    print(f"{indent}Merging: {left} + {right} => {merged}")
    return merged

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Demo call
arr = [8, 3, 5, 4, 7, 6, 1, 2]
sorted_arr = merge_sort(arr)
print("Final sorted array:", sorted_arr)

Output example:

Splitting: [8, 3, 5, 4, 7, 6, 1, 2]
  Splitting: [8, 3, 5, 4]
    Splitting: [8, 3]
      Returning: [8]
      Returning: [3]
    Merging: [8] + [3] => [3, 8]
...

5. Tips, Optimizations, and Real-World Use

Stable Sorting: Merge sort preserves the order of equal elements, making it a stable sort. This is beneficial when sorting objects by multiple fields.

Space Complexity: Since it uses extra space (creating new arrays during merge), its space complexity is O(n). In-place versions exist but are much more complex.

Python Tip: Python’s built-in sorted and list.sort() methods use Timsort, a hybrid of merge and insertion sort optimized for real-world data.

Use Case: Merge sort is ideal for sorting linked lists due to efficient node manipulation and avoiding random-access costs.

Further Idea: Visualize the algorithm with libraries like graphviz or matplotlib to animate the recursion tree.

Conclusion

Merge sort elegantly combines recursion and algorithmic thinking. We've broken it down step-by-step, visualized the recursion tree, and explained the core logic in both code and concept. Whether you're preparing for technical interviews or deepening your algorithmic intuition, mastering merge sort is a foundational win.

Now go ahead—modify it, optimize it, and maybe even animate it.

Useful links: