Merge Sort Explained Step by Step With Code

Merge sort is the sorting algorithm that never has a bad day. Most sorts have a worst case that drags them down. Merge sort does not. It is fast every single time.

The cost of that reliability is some extra memory. Most tutorials draw the splitting and then rush the merge, but the merge is where the real work happens. So that is where we will slow down.

What is merge sort?

Merge sort is a way to sort a list using a simple plan. Split the list in half. Sort each half. Then merge the two sorted halves into one sorted list.

The clever part is how it sorts each half. It splits them again, and again, until every piece holds just one item. A single item is already sorted by itself. So the real work is putting those tiny pieces back together in order.

This split and combine idea is called divide and conquer, the same family as quick sort. Because it keeps calling itself on smaller halves, merge sort leans on recursion.

How does merge sort work step by step?

Reading the plan is not enough. You have to watch the pieces split and join. So let’s sort the list [38, 27, 43, 3] by hand.

First the splitting. Cut [38, 27, 43, 3] into [38, 27] and [43, 3]. Cut again into [38], [27], [43], and [3]. Now every piece holds one item, so the splitting stops.

Now the merging, which is the real work. Merge [38] and [27] by comparing them, giving [27, 38]. Merge [43] and [3] the same way, giving [3, 43]. Two sorted pairs remain.

The final merge joins [27, 38] and [3, 43]. Compare the fronts, 27 and 3, and take the smaller, 3. Compare 27 and 43, take 27. Compare 38 and 43, take 38. Only 43 is left, so it goes last. The result is [3, 27, 38, 43], fully sorted.

Merge sort code in Python and C++

The code has two parts. One function splits the list and calls itself. A helper merges two sorted lists. Here it is in Python.

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

The merge function walks both lists at once, always taking the smaller front item. The leftover tail gets added at the end. Here is the same idea in C++, the language most Indian placement tests expect.

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2)
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

Both versions split until the pieces are tiny, then merge upward. The merge step is identical in spirit, comparing fronts and taking the smaller.

What is the time complexity of merge sort?

Merge sort runs in O(n log n) time, and this is its best feature. That holds in the best case, the average case, and the worst case. There is no bad input that slows it down. The log part comes from the halving, and the n part comes from merging all the items at each level.

For a list of a million items, that is around 20 million steps, not a trillion like the slow sorts. The catch is space. Merge sort uses O(n) extra memory to hold the pieces while merging. You can read the formal details on Wikipedia’s merge sort page.

When should you use merge sort?

Reach for merge sort when you need a guarantee. If you cannot risk a slow worst case, its steady O(n log n) is exactly right. It is also the go to when you need a stable sort, where equal items must keep their original order.

It shines on huge data that does not fit in memory, since it can sort pieces from disk and merge them. The main reason to skip it is the extra memory. When space is tight and you want in place sorting, quick sort is often the better pick. Both beat simple sorts like bubble sort by a wide margin.

FAQ

What is the time complexity of merge sort?

O(n log n) in the best, average, and worst cases. It never has a slow input. The space is O(n), because it needs extra memory to merge the pieces.

Why is merge sort always O(n log n)?

Because it always splits the list evenly in half, no matter the input. The even split is what keeps the worst case from ever appearing, unlike quick sort.

Is merge sort stable?

Yes. When two items are equal, the merge step keeps the one from the left half first, so equal items hold their original order. That property is called stability.

What is the difference between merge sort and quick sort?

Both are divide and conquer. Quick sort is usually faster and sorts in place, but can hit O(n squared). Merge sort is always O(n log n) and stable, but uses extra memory.

Why does merge sort use extra memory?

Because it builds new lists while merging the sorted pieces, rather than rearranging the original in place. That temporary space adds up to O(n).

Is merge sort good for large datasets?

Yes, especially data too big for memory. It can sort chunks separately and merge them, which is why it is common in external and database sorting.

So what should you remember?

Merge sort splits a list down to single items, then merges them back in order. That even splitting gives it a speed guarantee no input can break, plus stability for free.

The price is extra memory. When you need reliable speed or stable order, merge sort is the safe choice. When memory is tight, look to quick sort instead.

Now try the merge step yourself. Merging the two sorted halves [3, 27] and [38, 43], which value gets placed first?