Merge Sort

In the previous lesson, we studied basic sorting techniques such as Bubble Sort, Selection Sort, and Insertion Sort.

Those algorithms helped us understand how sorting works, but they are not efficient for large inputs.

Now we move to our first efficient sorting algorithm: Merge Sort.

The Main Idea Behind Merge Sort

Merge Sort is based on the Divide and Conquer strategy.

Instead of trying to sort the entire list at once, Merge Sort:

Breaks the list into smaller parts, sorts each part, and then merges them back together in a sorted way.

The key idea is simple:

It is easier to sort small lists than one large list.

Divide and Conquer Explained Simply

Divide and Conquer works in three steps:

First, divide the problem into smaller subproblems.

Second, solve each subproblem independently.

Finally, combine the solutions to solve the original problem.

Merge Sort uses recursion to apply this idea repeatedly.

How Merge Sort Works Step by Step

Suppose we have the list:

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

Merge Sort will:

Split the list into two halves. Then split each half again. This continues until each sublist contains only one element.

Since a single element is already sorted, the algorithm then starts merging the sublists back together in sorted order.

Merge Sort Algorithm (Code)

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)

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

arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))

This code shows how recursion divides the array and how the merge function combines sorted halves.

Why Merge Sort Is Faster

Merge Sort divides the array logarithmically and performs linear work while merging.

This results in a time complexity of:

O(n log n)

This is a huge improvement over the O(n²) algorithms we studied earlier.

Space Complexity Consideration

Merge Sort requires extra space to store temporary arrays during merging.

Because of this, Merge Sort is not an in-place algorithm.

Space complexity: O(n)

Real-World Usage

Merge Sort is widely used when stability is important.

It is commonly used in:

External sorting, large datasets, and systems where data is stored on disk.

Mini Practice

Think carefully:

• Why does Merge Sort always divide the list in half?
• Why is Merge Sort more predictable than Quick Sort?

Exercises

Quick Quiz

In the next lesson, we will study Quick Sort and see how a different divide-and-conquer strategy can perform even faster in practice.