Merge Sort Explained

Merge sort is a divide-and-conquer algorithm that sorts by splitting an array in half, recursively sorting each half, and then merging the two sorted halves back together. It guarantees O(n log n) time in every case — best, average, and worst — which makes it dramatically faster than O(n2) sorts like bubble sort on large data. The trade-off is that it needs O(n) extra space for the merge step.

The divide-and-conquer idea

Merge sort rests on a simple observation: merging two already-sorted lists into one sorted list is easy and fast. So the algorithm keeps splitting the array in half until each piece has a single element (which is trivially sorted), then merges pieces back together, two at a time, until the whole array is sorted.

The splitting forms a tree of depth log n (you can only halve n about log2(n) times), and merging at each level touches all n elements. Multiply those together and you get the O(n log n) running time.

Merge sort in C++

#include <iostream>
#include <vector>
using namespace std;

// Merge two sorted halves arr[left..mid] and arr[mid+1..right]
// into one sorted run. This step is O(n) for the range.
void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp;                 // holds the merged result
    int i = left, j = mid + 1;

    // Repeatedly take the smaller front element of the two halves.
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {       // <= keeps equal elements stable
            temp.push_back(arr[i++]);
        } else {
            temp.push_back(arr[j++]);
        }
    }
    while (i <= mid)   temp.push_back(arr[i++]);   // leftover from left half
    while (j <= right) temp.push_back(arr[j++]);   // leftover from right half

    for (int k = 0; k < (int)temp.size(); k++) {
        arr[left + k] = temp[k];      // copy merged run back into place
    }
}

// Recursively sort arr[left..right]. O(n log n) time overall.
void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;        // BASE CASE: zero or one element
    int mid = left + (right - left) / 2; // avoids overflow vs (left+right)/2
    mergeSort(arr, left, mid);        // sort the left half
    mergeSort(arr, mid + 1, right);   // sort the right half
    merge(arr, left, mid, right);     // combine the two sorted halves
}

int main() {
    vector<int> arr = {5, 2, 9, 1, 6, 3};
    mergeSort(arr, 0, arr.size() - 1);
    for (int x : arr) cout << x << " "; // 1 2 3 5 6 9
    return 0;
}

The recursion handles the dividing; the merge function handles the conquering. Note the <= in the comparison — that is what keeps merge sort stable, preserving the order of equal elements.

Why it is always O(n log n)

Unlike quick sort, which can degrade to O(n2) on bad pivots, merge sort splits exactly in half every time, so the recursion depth is always log n and each level always does O(n) merging work. There is no input that breaks it. This predictability is valuable when you cannot tolerate a slow worst case.

The space cost

Merge sort's main weakness is memory. The merge step builds a temporary array, so it uses O(n) extra space beyond the input. For sorting in place with no extra memory, quick sort is usually preferred. But merge sort's stability and guaranteed performance make it the algorithm of choice for sorting linked lists and for external sorting of data too large to fit in memory.

When to use merge sort

Choose merge sort when you need guaranteed O(n log n) performance regardless of input, when stability matters (sorting records by one field without disturbing another), or when sorting a linked list, where it merges without the random access that arrays need. Avoid it when memory is tight and an in-place sort would serve.

Common mistakes

• Computing mid as (left + right) / 2. For large indices this can overflow. Use left + (right - left) / 2.
• Wrong base case. The recursion must stop at a single element (left >= right). A wrong condition either infinite-loops or skips merging.
• Breaking stability. Using < instead of <= when both fronts are equal can swap the order of equal elements. Use <= to keep it stable.
• Forgetting the leftover elements. After the main merge loop, one half may still have elements. Both trailing while loops are required to copy them.
• Ignoring the space cost. Allocating a temporary array on every merge adds up. Be aware merge sort is not in place when memory is constrained.

FAQ

Merge sort or quick sort? Merge sort guarantees O(n log n) and is stable but uses O(n) space. Quick sort is in place and often faster in practice but has an O(n2) worst case. Pick based on whether you need the guarantee and stability.

Why is it good for linked lists? Merge sort only needs sequential access to merge, which linked lists provide cheaply, and it can splice nodes without extra arrays — avoiding the random access that hurts other sorts.

Keep learning

Compare it with Quick Sort, see the recursion technique it relies on in Recursion Problems & Patterns, and browse the full DSA hub.

Want to implement merge sort with instructor feedback in Jalgaon? Join the waitlist for our Data Structures & Algorithms course.