Comparison Sorts: Merge Sort and Quicksort

March 2026 · 35 min read

Merge sort and quicksort are the two most important sorting algorithms in computer science. Both use divide and conquer, but they divide differently: merge sort does the hard work during the merge step, while quicksort does the hard work during the partition step.

This post covers both algorithms in full detail. We will trace through every step with interactive SVG animations, write production-quality C++ code, analyze the recurrences, compare the two, and understand when to pick one over the other.

Merge Sort

Merge sort was invented by John von Neumann in 1945. It is the simplest $O(n \log n)$ sorting algorithm and the easiest to prove correct. The idea is straightforward:

1. Divide: split the array into two halves.
2. Conquer: recursively sort each half.
3. Combine: merge the two sorted halves into one sorted array.

The beauty of merge sort is that the merge step is where all the real work happens. Dividing costs nothing (just compute the midpoint). Merging two sorted arrays of total length $n$ takes exactly $O(n)$ time. Since we halve the array $\log n$ times and do $O(n)$ work at each level, the total time is $O(n \log n)$.

The Recurrence

The time complexity satisfies the recurrence:

By the Master Theorem (case 2), this gives $T(n) = O(n \log n)$. This holds in the best, average, and worst case. Merge sort always divides evenly and always merges, regardless of the input.

The Merge Operation

Given two sorted sub-arrays left[] and right[], merging works as follows:

1. Maintain two pointers, one at the start of each sub-array.
2. Compare the elements at both pointers.
3. Copy the smaller element to the output array and advance that pointer.
4. When one sub-array is exhausted, copy the remaining elements from the other.

This process takes $O(n)$ time and $O(n)$ space for the output array.

C++ Implementation

void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> tmp;
    int i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j])  // <= preserves stability
            tmp.push_back(arr[i++]);
        else
            tmp.push_back(arr[j++]);
    }
    while (i <= mid)  tmp.push_back(arr[i++]);
    while (j <= right) tmp.push_back(arr[j++]);
    for (int k = left; k <= right; k++)
        arr[k] = tmp[k - left];
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

Properties of Merge Sort

• Time: $O(n \log n)$ in all cases (best, average, worst).
• Space: $O(n)$ auxiliary space for the temporary array.
• Stable: Yes, when using <= in the merge comparison.
• Adaptive: No, it always does the same number of comparisons regardless of input order.
• In-place: No. Standard merge sort requires $O(n)$ extra memory.

Recursion Tree Visualization

The recursion tree helps visualize the work at each level. At every level, the total work is $O(n)$ because we process every element exactly once (either in a split or a merge). There are $\log_2 n$ levels, giving $O(n \log n)$ total.

Quicksort

Quicksort was invented by Tony Hoare in 1959. It is the fastest comparison-based sort in practice for most inputs. The idea:

1. Partition: pick a pivot element and rearrange the array so that all elements less than the pivot come before it, and all elements greater come after it.
2. Recurse: sort the left partition and the right partition independently.

Unlike merge sort, quicksort does not need a merge step. Once the partitions are sorted, the entire array is sorted. The hard work happens during partitioning.

Lomuto Partition Scheme

The Lomuto partition is the simpler of the two standard schemes. It uses the last element as the pivot and maintains a boundary index i that separates elements less than or equal to the pivot from those greater.

int lomutoPartition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = lomutoPartition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Hoare Partition Scheme

Hoare's original partition scheme is more efficient than Lomuto's because it does fewer swaps on average. It uses two pointers that start at opposite ends and move toward each other.

int hoarePartition(vector<int>& arr, int low, int high) {
    int pivot = arr[low];
    int i = low - 1, j = high + 1;
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;
        swap(arr[i], arr[j]);
    }
}

void quickSortHoare(vector<int>& arr, int low, int high) {
    if (low < high) {
        int p = hoarePartition(arr, low, high);
        quickSortHoare(arr, low, p);
        quickSortHoare(arr, p + 1, high);
    }
}

Lomuto vs Hoare

Pivot Selection Strategies

The choice of pivot determines quicksort's performance. A bad pivot leads to unbalanced partitions and $O(n^2)$ time.

Strategy 1: First or Last Element

Simple but dangerous. If the array is already sorted or reverse-sorted, the pivot is always the minimum or maximum, creating partitions of size 0 and $n-1$. This gives $O(n^2)$ time.

Strategy 2: Random Pivot

Pick a random index and swap the element there to the pivot position before partitioning. This makes the worst case extremely unlikely. Expected time is $O(n \log n)$ for any input.

int randomPartition(vector<int>& arr, int low, int high) {
    int randIdx = low + rand() % (high - low + 1);
    swap(arr[randIdx], arr[high]);
    return lomutoPartition(arr, low, high);
}

Strategy 3: Median of Three

Choose the median of the first, middle, and last elements as the pivot. This avoids the worst case on sorted and reverse-sorted inputs, which are common in practice.

int medianOfThree(vector<int>& arr, int low, int high) {
    int mid = low + (high - low) / 2;
    if (arr[mid] < arr[low]) swap(arr[low], arr[mid]);
    if (arr[high] < arr[low]) swap(arr[low], arr[high]);
    if (arr[high] < arr[mid]) swap(arr[mid], arr[high]);
    swap(arr[mid], arr[high]);  // place median at high
    return lomutoPartition(arr, low, high);
}

Worst Case Analysis

Quicksort's worst case happens when every partition is maximally unbalanced: one side has 0 elements and the other has $n-1$. This gives the recurrence:

Solving by expansion:

This happens when:

• The array is already sorted and we always pick the first or last element as pivot.
• All elements are identical (with Lomuto partition).

Average Case

On average, the pivot lands near the middle, splitting the array into roughly equal halves. The recurrence becomes:

This gives $O(n \log n)$, same as merge sort. In practice, quicksort is faster than merge sort because:

• Smaller constant factors (fewer data movements).
• In-place partitioning is cache-friendly.
• The inner loop is tight and branch-predictable.

Three-Way Partition (Dutch National Flag)

When the array contains many duplicates, standard quicksort degrades because equal elements end up on one side of the pivot. The three-way partition groups elements into three regions: less than pivot, equal to pivot, greater than pivot.

void threeWayQuickSort(vector<int>& arr, int low, int high) {
    if (low >= high) return;
    int lt = low, gt = high, i = low;
    int pivot = arr[low];
    while (i <= gt) {
        if (arr[i] < pivot)
            swap(arr[lt++], arr[i++]);
        else if (arr[i] > pivot)
            swap(arr[i], arr[gt--]);
        else
            i++;
    }
    // arr[lt..gt] are all equal to pivot
    threeWayQuickSort(arr, low, lt - 1);
    threeWayQuickSort(arr, gt + 1, high);
}

Merge Sort vs Quicksort

When to Use Which

• Need guaranteed O(n log n): Use merge sort.
• Need stability: Use merge sort.
• Need fastest average case, in-place: Use quicksort with random pivot.
• Linked lists: Merge sort is clearly better (no random access needed, O(1) extra space).
• External sorting (data on disk): Merge sort, because it accesses data sequentially.
• Arrays with many duplicates: Quicksort with three-way partition.

Summary

• Merge sort splits first, then merges. Quicksort partitions first, then recurses. Both are divide and conquer.
• Merge sort is $O(n \log n)$ always but needs $O(n)$ extra space. Quicksort is $O(n \log n)$ on average and in-place, but can degrade to $O(n^2)$.
• Lomuto partition is simpler; Hoare partition does fewer swaps. Use random or median-of-three pivot to avoid worst case.
• For arrays with many duplicates, use three-way partition.
• In C++, std::sort uses introsort (quicksort + heapsort fallback), and std::stable_sort uses merge sort.