Understanding Merge Sort in Python: A Recursive Divide and Conquer Algorithm

[Rajeev Bagra]

1. Most beginners first encounter sorting algorithms such as Bubble Sort, Selection Sort, and Insertion Sort. While these algorithms are excellent for learning fundamental sorting concepts, they become inefficient when working with large datasets.

Merge Sort takes a different approach. Instead of repeatedly swapping elements, it divides a large problem into smaller problems, solves those smaller problems, and then combines the results.

This technique is known as Divide and Conquer.

---

Is Merge Sort Recursive?

Yes.

Merge Sort is traditionally implemented using recursion. The function repeatedly calls itself on smaller portions of the array until each portion contains only one element.

The recursive nature of Merge Sort makes it a classic example of the Divide and Conquer strategy.

---

The Three Steps of Merge Sort

Every Merge Sort operation follows three simple steps:

1. Divide

Split the array into two smaller halves.

mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]

2. Conquer

Recursively sort both halves.

left_half = merge_sort(left_half)
right_half = merge_sort(right_half)

3. Combine

Merge the sorted halves into one sorted array.

return merge(left_half, right_half)

---

Complete Python Code

def merge_sort(arr):

    # Base case
    if len(arr) <= 1:
        return arr

    # Divide
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # Recursively sort both halves
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    # Merge sorted halves
    return merge(left_half, right_half)


def merge(left, right):

    result = []
    i = 0
    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

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

    return result


numbers = [38, 27, 43, 3, 9, 82, 10]

sorted_numbers = merge_sort(numbers)

print(sorted_numbers)

---

Output

[3, 9, 10, 27, 38, 43, 82]

---

Where Does the Recursion Happen?

The recursive calls occur here:

left_half = merge_sort(left_half)
right_half = merge_sort(right_half)

Notice that the function merge_sort() calls itself.

This continues until the subarray contains only one element.

---

Visualizing the Recursive Calls

Suppose we start with:

[38, 27, 43, 3, 9]

The recursive calls look like:

merge_sort([38,27,43,3,9])

├── merge_sort([38,27])
│   ├── merge_sort([38])
│   └── merge_sort([27])
│
└── merge_sort([43,3,9])
    ├── merge_sort([43])
    └── merge_sort([3,9])
        ├── merge_sort([3])
        └── merge_sort([9])

Each branch continues until only one element remains.

---

The Base Case

Every recursive algorithm requires a stopping condition, known as the base case.

In Merge Sort, the base case is:

if len(arr) <= 1:
    return arr

Why?

Because an array containing one element is already sorted.

Without this condition, the function would continue calling itself forever.

---

Step-by-Step Example

Consider:

[8, 3, 5, 4]

Divide

[8, 3, 5, 4]

      /      \
 [8, 3]    [5, 4]

Divide Again

[8] [3]   [5] [4]

Merge

[3, 8]   [4, 5]

Final Merge

[3, 4, 5, 8]

The array is now completely sorted.

---

Time Complexity

Case	Complexity
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n log n)

One of the biggest advantages of Merge Sort is that its performance remains consistent regardless of the initial order of the data.

---

Can Merge Sort Be Implemented Without Recursion?

Yes.

A variation called Bottom-Up Merge Sort uses an iterative approach and does not require recursion.

However, the recursive version is much easier to understand and is the version most commonly taught in computer science courses.

---

Key Takeaway

Merge Sort is a classic Divide and Conquer algorithm that relies on recursion to repeatedly split an array into smaller pieces. Once each piece contains a single element, the algorithm merges the pieces back together in sorted order.

The recursive calls:

merge_sort(left_half)
merge_sort(right_half)

are the heart of the algorithm and demonstrate how a complex sorting problem can be solved by breaking it into many smaller, simpler problems.

[Author]

Posts