Sorting in C++: Five Algorithms, Stability, and What the Merge Step Buys You

Posted on by NY Comdori

Almost nobody implements a sorting algorithm at work. You call std::sort and move on. So the usual defence of learning them — “it builds fundamentals” — is doing a lot of unpaid labour in that sentence.

Here is a better reason, and it is the one this post is built on. Three of the five algorithms below contain a reusable subroutine that shows up as LeetCode problems in its own right. Merge sort’s merge step is a problem. Quicksort’s partition step is four problems. And one character inside merge sort decides whether the algorithm is stable, which changes what you are allowed to build on top of it.

This is the first of three posts working through Joseph Choi’s sorting session deck in C++. Everything here was compiled with -Wall -Wextra -Wshadow -fsanitize=undefined,address under both C++17 and C++20, and checked against a reference implementation on tens of thousands of random inputs before the prose was written. The stability and worst-case numbers in the closing section are measured.

Why sorting is worth the time

The deck opens with the practical case: your inbox is sorted by timestamp, a leaderboard by score, search results by relevance and recency. Sorting is used far more than we notice, usually as a preprocessing step rather than as the answer.

That last part is the interesting bit, and it is the theme of all three posts. Sorting is rarely the solution to a problem. It is the thing that makes the solution possible — it converts “search everywhere” into “walk once,” and it converts a hash map into a pair of indices. The algorithms below are worth knowing not as trivia but because their internals are the reusable parts.

The two quadratic ones

Selection and insertion sort are usually taught as a warm-up and then dismissed. Both have a real niche, and they differ in a way that turns out to matter more than their shared O(n²).

Selection sort

The deck’s framing is the card-game one: you are holding a hand of cards, and you repeatedly pick the smallest from the unsorted part and put it at the front of the sorted part. Once a card is placed you never touch it again.

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) if (arr[j] < arr[minIndex]) minIndex = j;
        if (minIndex != i) swap(arr[i], arr[minIndex]);
    }
}

Two nested loops, both of which always run to completion, so it is O(n²) on every input including an already-sorted one. There is no best case.

What it does have is the deck’s own observation: it makes at most n − 1 swaps. Every other comparison sort moves data more than that. If you are sorting something where writes are expensive and comparisons are cheap — flash memory with limited write cycles, or records so large that moving one costs far more than comparing two — selection sort’s write count is a genuine advantage. That is the niche, and it is narrow, but it is real.

Insertion sort

Same shape, opposite strategy. Instead of searching the unsorted part for the next smallest, take the next element and shift it left through the sorted part until it lands.

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i], j = i - 1;
        while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
        arr[j + 1] = key;
    }
}

The inner loop is a while with a data-dependent condition, and that single difference gives insertion sort a best case that selection sort does not have. On already-sorted input, arr[j] > key is false immediately, the inner loop never runs, and the whole thing is O(n) — one pass, no shifts.

This is why insertion sort is not a museum piece. It is genuinely the fastest thing available on small or nearly-sorted input, which is why real library sorts use it: std::sort is typically introsort, which switches to insertion sort once a partition gets small enough. The quadratic algorithm you were told to forget is running inside the one you actually call.

Note also that the shift is arr[j] > key and not >=. That stops the loop at the first element that is not strictly greater, which means an element equal to key stays to its left. Hold onto that — it is the whole of the stability section.

The two that divide and conquer

Merge sort

Split the array in half, sort each half, then merge the two sorted halves. The recursion is trivial; all the content is in the merge.

void merge_(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1, n2 = right - mid;
    vector<int> leftArray(n1), rightArray(n2);
    for (int i = 0; i < n1; i++) leftArray[i] = arr[left + i];
    for (int j = 0; j < n2; j++) rightArray[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArray[i] <= rightArray[j]) arr[k++] = leftArray[i++];   // <= is what makes it stable
        else arr[k++] = rightArray[j++];
    }
    while (i < n1) arr[k++] = leftArray[i++];
    while (j < n2) arr[k++] = rightArray[j++];
}
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);
}

O(n log n) on every input — best, average and worst — because the split is always down the middle regardless of the data. The cost is O(n) extra space for the temporary arrays, and that is not an implementation detail you can optimise away: merging two sorted runs in place is possible but substantially slower and much harder to get right.

The line to look at is if (leftArray[i] <= rightArray[j]). When the two candidates are equal, that <= takes the one from the left half — the one that came first in the original array. Change it to < and the algorithm still sorts correctly, still runs in O(n log n), and passes every test that only checks the output order. It just stops being stable. I measured what that costs in the next section.

Quicksort

Also divide and conquer, but it does the work before recursing rather than after. Pick a pivot, rearrange the array so everything smaller is left of it and everything larger is right of it, and the pivot is then in its final position. Recurse on each side. There is no merge step, because the partition already put things in the right regions.

int partition_(vector<int>& arr, int low, int high) {
    int pivot = arr[high], 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) return;
    int p = partition_(arr, low, high);
    quickSort(arr, low, p - 1); quickSort(arr, p + 1, high);
}

That is the Lomuto partition scheme with the last element as pivot. i tracks the end of the “smaller than pivot” region; every element that belongs there gets swapped into it, and at the end the pivot is swapped into the gap.

Average O(n log n), worst case O(n²), and the deck asks the right question: why is it faster than merge sort in practice when the average complexity is identical? Two reasons. It sorts in place, so there is no allocation and no copying into temporaries. And it has excellent locality — the partition loop is a single linear scan, which is exactly what a CPU prefetcher wants.

The worst case is not hypothetical, and “pick the last element” is what causes it. On already-sorted input every partition splits the array into one element and everything else, so the recursion is n levels deep and does n work per level. Measured, with the comparison count instrumented:

nComparisons, already-sorted inputComparisons, random inputn²/2n log₂ n
1,000499,50011,183500,0009,966
2,0001,999,00023,2952,000,00021,932
4,0007,998,00059,8228,000,00059,822

Sorted input lands on exactly n(n−1)/2 comparisons — the theoretical worst case, to the comparison. At n = 4,000 that is 134 times the work the same code does on random input. Sorted or reverse-sorted data is not an exotic adversarial case; it is the most likely shape real data arrives in.

The fix is to not let the input choose your pivot. Randomising it makes the bad case astronomically unlikely rather than guaranteed, and that is exactly what the deck does when the same partition routine is reused for quickselect — rand() % (right - left + 1) + left. Worth noticing that the deck writes the teaching version with a fixed pivot and the production version with a random one.

Stability, and the one character that decides it

A sort is stable if elements with equal keys come out in the same relative order they went in. The deck’s example is the clearest one: sort [(4,'a'), (2,'b'), (4,'c'), (3,'d')] by the number, and a stable sort gives (4,'a') before (4,'c'), because ‘a’ came first in the input.

This sounds like a footnote and is not. Here is why it matters, which is the deck’s own list: stability is what lets you sort by multiple keys with repeated single-key sorts. Sort by name, then sort by department, and a stable sort leaves each department’s people still in name order. An unstable sort scrambles them, and you have to write a comparator that handles both keys at once instead.

The deck gives a table of which algorithms are stable and why. I ran it rather than taking it on trust — 20,000 random inputs of length 2 to 9 drawn from just three distinct keys, so equal keys are everywhere, checking each algorithm’s output against std::stable_sort:

AlgorithmInputs where order was not preservedWhy
Insertion0 / 20,000shifts only while arr[j] > key, so equals are never crossed
Merge, with <=0 / 20,000on a tie the left half wins, and the left half came first
Merge, with <17,764 / 20,000on a tie the right half wins, reversing equal elements
Selection8,880 / 20,000the swap moves a distant element over equal ones
Quick9,040 / 20,000partition swaps across the array without regard to order

The third row is the one to take away. Merge sort’s stability is not a property of the divide-and-conquer structure — it is a property of one comparison operator in the merge step, and flipping it breaks stability on 89% of inputs while leaving the sort order perfectly correct. That is a bug that no output-comparison test will ever find.

In C++ this is why std::sort and std::stable_sort are two functions rather than one. std::sort makes no stability guarantee and is typically introsort — quicksort with a heapsort fallback and insertion sort for small runs. std::stable_sort promises stability and is typically a merge sort, which is why it may allocate.

The merge step, on its own

Now the payoff. Merge sort’s inner loop — walk two sorted sequences with one index each, advance whichever is behind — is a technique in its own right, and three problems in the deck are exactly that loop with the body changed.

Intersection of Two Arrays (LC 349, Easy)

The deck names both options honestly: use a hash set, or sort and walk. The hash set is O(n + m) time and the obvious answer. Sorting is O(n log n + m log m), which is worse — so why would you?

Because of the deck’s follow-up question: how do you improve the space complexity? A hash set holds up to n elements. The two-pointer walk holds nothing beyond the output. When the arrays are already sorted, or too large to fit a hash table over, or arriving as streams you can only read forwards, the sorted walk is the only one of the two that works at all.

vector<int> intersection349(vector<int>& nums1, vector<int>& nums2) {
    unordered_set<int> result;
    sort(begin(nums1), end(nums1)); sort(begin(nums2), end(nums2));
    int i = 0, j = 0;
    while (i < (int)nums1.size() && j < (int)nums2.size()) {
        if (nums1[i] == nums2[j]) { result.insert(nums1[i]); ++i; ++j; }
        else if (nums1[i] < nums2[j]) ++i; else ++j;
    }
    return vector<int>(begin(result), end(result));
}

Three cases, and this is the shape to memorise: equal means take it and advance both, otherwise advance whichever pointer is pointing at the smaller value. Advancing only the smaller one is what guarantees you never skip a match.

The unordered_set for the result is doing deduplication, not lookup — the problem wants each common value once, and duplicates within one input array would otherwise produce repeats. It also means the returned order is unspecified, which LC 349 permits.

Intersection of Three Sorted Arrays (LC 1213, Easy, Premium)

Note: LC 1213 is a LeetCode Premium problem, so viewing it needs a paid subscription. Three strictly-increasing arrays; return the values present in all three, in order.

vector<int> arraysIntersection(vector<int>& a1, vector<int>& a2, vector<int>& a3) {
    vector<int> result; int i = 0, j = 0, k = 0;
    while (i < (int)a1.size() && j < (int)a2.size() && k < (int)a3.size()) {
        if (a1[i] == a2[j] && a2[j] == a3[k]) { result.push_back(a1[i]); ++i; ++j; ++k; }
        else if (a1[i] < a2[j] || a1[i] < a3[k]) ++i;
        else if (a2[j] < a1[i] || a2[j] < a3[k]) ++j;
        else ++k;
    }
    return result;
}

The same loop with three indices. All three equal means take it and advance all three; otherwise advance any pointer that is strictly behind another. The conditions read oddly — arr1[i] < arr2[j] || arr1[i] < arr3[k] — but the logic is sound: if the value at i is behind either of the others it cannot be part of a common triple, so it is safe to discard.

No sort is needed here because the problem hands you sorted input, so this is O(n + m + k) with O(1) extra space. It also generalises: the natural extension to k sorted lists is a heap holding one candidate per list, which is precisely the structure that Employee Free Time uses in the next post.

Merge Sorted Array (LC 88, Easy)

The deck is explicit that this is merge sort’s merge step, and then asks the question that makes the problem interesting: you have to write the result into nums1, which is also one of the inputs. Do you fill from the front or the back? And what goes wrong with the front?

What goes wrong is that filling forward overwrites nums1 entries you have not read yet. On nums1 = [1,2,3,0,0,0] with nums2 = [2,5,6], the first write puts 1 at index 0 — harmless — but the moment a nums2 value wins, it lands on top of a live nums1 value. You would need a temporary copy, which costs the O(1) space that makes this problem worth asking.

void merge88(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int idx1 = m - 1, idx2 = n - 1;
    for (int i = (int)nums1.size() - 1; i >= 0; --i) {
        if (idx1 >= 0 && idx2 >= 0) nums1[i] = nums1[idx1] >= nums2[idx2] ? nums1[idx1--] : nums2[idx2--];
        else if (idx1 >= 0) nums1[i] = nums1[idx1--];
        else nums1[i] = nums2[idx2--];
    }
}

Filling from the back is free of that hazard, and the reason is worth stating precisely: the write position i is always at or ahead of both read positions, because there are exactly m + n values to place into m + n slots. The space you are writing into is space you have already consumed. That argument is the entire trick, and it recurs any time you compact or merge in place.

The >= in the ternary is the stability operator again, in a problem that does not need stability — with equal values it takes from nums1 first. Since we are filling from the largest end downwards, taking the nums1 copy first places it later in the output, which preserves the original relative order. Same idea as the merge step, mirrored.

The five algorithms on one page

AlgorithmBestAverageWorstSpaceStableUse it when
SelectionO(n²)O(n²)O(n²)O(1)Nowrites are expensive — at most n−1 swaps
InsertionO(n)O(n²)O(n²)O(1)Yessmall or nearly-sorted input
MergeO(n log n)O(n log n)O(n log n)O(n)Yesyou need stability or a guaranteed bound
QuickO(n log n)O(n log n)O(n²)O(log n)Nogeneral in-memory sorting; randomise the pivot
Heap (not in the deck)O(n log n)O(n log n)O(n log n)O(1)Noguaranteed bound with no extra space

Quicksort’s O(log n) space is the recursion stack, not a buffer. Heapsort is not in the deck but earns a row, because it is the only entry that is both worst-case O(n log n) and in place — which is why introsort falls back to it rather than to merge sort.

Misfits, edge cases, and the things that bite

The stability bug no test will catch

Covered above but it belongs on any list of quiet failures. Merge sort with < instead of <= sorts correctly and is unstable on 89% of inputs with repeated keys. If the only assertion you write is “the output is in order,” you will never see it — and the failure surfaces later, in whatever code assumed it could sort by a second key first.

A fixed pivot makes sorted input the worst case

Measured above: 7,998,000 comparisons versus 59,822 at n = 4,000, a factor of 134. The dangerous part is the direction of the surprise — people expect already-sorted input to be the easy case, and for insertion sort it is. For textbook quicksort it is the catastrophe. If you ever ship a Lomuto partition with a fixed pivot, randomise it or take a median of three.

Unsigned arithmetic on size()

vector::size() returns an unsigned type, and several listings in this deck compare an int loop index against it or subtract from it. nums1.size() - 1 on an empty vector is not −1; it is 18,446,744,073,709,551,615. Every version in this post hoists the size into an int first, which removes the whole class of problem and silences the -Wsign-compare warnings the originals produce.

The two quadratic sorts are quietly fine here — int n = arr.size() followed by i < n - 1 gives i < -1 on an empty array and the loop simply does not run. That is only safe because n is signed. Write arr.size() - 1 directly in that condition and an empty array loops four billion times.

Empty input

LC 349’s loop handles empty arrays by not running. LC 88 with m = 0 works because the else branch drains nums2. But any solution that reaches for front() or back() before checking has undefined behaviour on empty input — the deck’s Merge Intervals does this, and it survives only because that problem guarantees at least one interval. I added the guard anyway in post two, because guarantees do not travel with copied code.

When a comparison sort is the wrong tool

  • The keys are small integers. Comparison sorts are bounded below by O(n log n). Counting sort and radix sort are not comparison sorts and can beat it — the deck lists them as “not covered,” and Sort Colors in post three is a counting-sort-shaped problem solved in one pass.
  • You only need part of the answer. Sorting to find the k largest elements is O(n log n) for an O(n) question. That is quickselect, and it is the whole first half of post three.
  • The data does not fit in memory. External merge sort exists precisely because merge sort only ever needs to read its inputs forwards, one element at a time — the same property that makes the merge step work on streams.
  • It is already sorted. Checking costs one linear pass. On nearly-sorted input insertion sort is O(n) and std::sort is not.

How to practise this

  1. Write the merge step from memory, including both drain loops. It is the single most reusable twenty lines in this post.
  2. Write the Lomuto partition from memory and be able to say what i means at every point. Post three reuses it four times.
  3. For any sort you write, state its stability out loud and point at the line that decides it.
  4. Test with duplicate keys, already-sorted input, reverse-sorted input, one element, and empty. Those five catch everything in the misfits section.
  5. Then do LC 88 → 349 → 1213, in that order. They are the merge step three times with a different body.

The rest of this series

Credit and the rest of the series

The problem selection, the ordering, and the framing come from Joseph Choi‘s sorting session deck — including the card-game intuition for selection sort, the stability table and its rationales, the front-versus-back question that makes LC 88 interesting, and the observation that quicksort matches merge sort’s complexity while beating it in practice. The C++ here is my own, rewritten where I preferred different types or an added guard, and every listing was compiled and differentially tested before publication.

Other pattern write-ups on this site: