Merge sort

Sort each half, then merge

Like organizing two stacks of already sorted cards, each time taking the smaller top card from the two stacks yields an overall sorted sequence.

Divide in half until the interval length is no more than 1; after the left and right recursion are complete, compare from the heads of both sides and write into a temporary array, then copy back to the original interval. Each level of merging is O(n) in total, the number of levels is O(log n), so the total time is O(n log n), and common implementations use O(n) extra space.

When equal, taking the left element first can preserve the original relative order of equal keys, so merge sort can be stable. Below, the half-open interval [l,r) is used, so the length is r−l.

Why merge sort takes O(n log n) time

Split [3, 1, 2, 1] into [3, 1] and [2, 1], then into single elements. Merge to [1, 3] and [1, 2], then to [1, 1, 2, 3].

1. Each split roughly halves the range, so the split depth is O(log n).
2. Across one merge level, the ranges contain n elements in total. Each merge scans its range linearly, giving O(n) work per level.
3. This implementation always merges and copies each level: best, average and worst time are all Θ(n log n) for n≥2.

The temporary array uses O(n) space and the recursive call depth uses O(log n), giving O(n) total auxiliary space. This implementation is not in place. Taking from the left half first on equal keys preserves stability. Other versions that skip already ordered merges can have different best-case behavior.

Half-open implementation and equal-key order

Example 1: Merge sort on a half-open interval

#include <iostream>
#include <vector>
using namespace std;
void mergeSort(vector<int>& a, vector<int>& tmp, int l, int r) {
    if (r - l <= 1) return;
    int m = l + (r - l) / 2;
    mergeSort(a, tmp, l, m); mergeSort(a, tmp, m, r);
    int i = l, j = m, k = l;
    while (i < m && j < r) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
    while (i < m) tmp[k++] = a[i++];
    while (j < r) tmp[k++] = a[j++];
    for (int p = l; p < r; ++p) a[p] = tmp[p];
}
int main() {
    vector<int> a = {3, 1, 2, 1}, tmp(a.size());
    mergeSort(a, tmp, 0, a.size());
    for (int x : a) cout << x << " ";
    cout << endl;
}

Output 1 1 2 3. The temporary array prevents overwriting original elements that have not yet been read, and after one side is exhausted, the remaining part of the other side must be copied.

Example 2: How to ensure stability when equal

The left half contains (score 80, A), and the right half contains (score 80, B). A originally appeared before B.

When the keys are equal, take the left one first, and the order remains unchanged after merging. If the right one is always taken first, equal elements may be reversed, and stability is lost.

Tips

• All recursion and merging use the same interval convention; closed intervals and half-open intervals must not be mixed.
• Stability depends on implementation details; choosing the right one when equal does not guarantee stability.
• Empty arrays and single-element intervals should return immediately, otherwise infinite recursion may occur.

Prerequisites

• Sorting algorithms
• Recursion

Technical references

• Stanford CS106B: sorting

Scope note

This lesson is written by InfoCode and is not an official syllabus; the reference level is a site mapping and does not represent official levels, certification or eligibility. Practice records do not establish mastery or eligibility.

Reference level: GESP Level 5 (site mapping)

See contest pathways