Identifying Sorting Algorithms from a Snapshot, and the Big-O Cheat Sheet

The five fingerprints

Read a snapshot in three steps.

Step 1 — find the sorted block. Scan for the longest contiguous run that is already in order.

Step 2 — ask which end it is at. Head or tail? Middle-of-array structure means merge or quicksort.

Step 3 — ask whether that block holds the global extremes. This is the step people skip, and it is the one that separates insertion sort from selection sort.

Two details that decide close calls:

• "Sorted" ≠ "final position." Insertion sort's prefix is sorted but almost every element in it will move again. Selection and bubble sort's blocks are genuinely finished. If a question asks "which elements are in their final position?", the answer for insertion sort is often none.
• Selection sort's tail is scrambled, insertion sort's tail is pristine. Selection sort swaps the displaced front element out into the tail, so you can often spot a value that has obviously teleported backwards. Insertion sort never writes past the current index, so the suffix is a verbatim copy of the input's suffix. This single check is the most reliable discriminator on the page.

One input, three quadratic sorts, real output

Everything below comes from running this program. Note the n - pass bound in bubble sort (the tail is finished, do not re-scan it) and the j >= 0 && ordering in insertion sort (&& short-circuits left to right; swap the operands and you read a[-1]).

The traces for input 25 41 29 37 10 14 13 6:

bubble  pass 1: 25 29 37 10 14 13  6 41      <- 41 settled
bubble  pass 2: 25 29 10 14 13  6 37 41      <- 37 settled
bubble  pass 3: 25 10 14 13  6 29 37 41      <- 29 settled, head still chaos

select  pass 1:  6 41 29 37 10 14 13 25      <- 6 to front; 25 flung to the back
select  pass 2:  6 10 29 37 41 14 13 25
select  pass 3:  6 10 13 37 41 14 29 25      <- head = 3 smallest, tail scrambled

insert  step 3: 25 29 37 41 10 14 13  6      <- prefix sorted, suffix = original
insert  step 5: 10 14 25 29 37 41 13  6      <- note 6 is NOT in the prefix

Compare bubble pass 3 with select pass 3. Same input, same number of passes, mirror-image structure. Compare select pass 3 with insert step 5: both have a sorted head, but selection's head is 6 10 13 (the global minima) while insertion's is 10 14 25 29 37 41 (which conspicuously lacks 6). That is the whole game.

One more high-value observation from the code: bubble sort's swapped flag is what gives it an O(n) best case. Without the flag it is Θ(n²) unconditionally. Selection sort has no equivalent trick — its inner loop must scan the entire remaining range to be sure it found the minimum, so it is Θ(n²) even on already-sorted input.

#include <iostream>
#include <vector>

void print(const std::vector<int>& a) {
    for (int x : a) std::cout << x << ' ';
    std::cout << '\n';
}

// After pass k: the k largest values are parked at the tail, in order.
void bubbleSort(std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    for (int pass = 0; pass < n - 1; ++pass) {
        bool swapped = false;
        for (int j = 0; j + 1 < n - pass; ++j)       // n - pass: tail is done
            if (a[j] > a[j + 1]) { std::swap(a[j], a[j + 1]); swapped = true; }
        std::cout << "bubble  pass " << pass + 1 << ": "; print(a);
        if (!swapped) break;                          // already sorted, bail out
    }
}

// After pass k: the k smallest values are parked at the head, in order.
void selectionSort(std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    for (int i = 0; i < n - 1; ++i) {
        int minIdx = i;
        for (int j = i + 1; j < n; ++j)
            if (a[j] < a[minIdx]) minIdx = j;
        if (minIdx != i) std::swap(a[i], a[minIdx]);
        std::cout << "select  pass " << i + 1 << ": "; print(a);
    }
}

// After step i: a[0..i] is sorted among itself; a[i+1..n-1] is untouched input.
void insertionSort(std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    for (int i = 1; i < n; ++i) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; --j; }  // j >= 0 FIRST
        a[j + 1] = key;
        std::cout << "insert  step " << i << ": "; print(a);
    }
}

int main() {
    const std::vector<int> input = {25, 41, 29, 37, 10, 14, 13, 6};
    std::vector<int> a;
    a = input; bubbleSort(a);    std::cout << '\n';
    a = input; selectionSort(a); std::cout << '\n';
    a = input; insertionSort(a);
    return 0;
}

Merge and quicksort snapshots — and the one genuine ambiguity

Quicksort is the easiest to recognise once you know what a partition guarantees. Partitioning 25 41 29 37 10 14 13 6 around pivot 29 produces:

25  6 10 14 13 | 29 | 41 37

Exactly one element is final. Both sides satisfy the pivot inequality and neither is sorted. Also note the pivot landed at index 5, not index 3 — a partition never promises balance, which is precisely why the worst case exists.

Merge sort has two different snapshot shapes depending on the variant, and this trips people up.

Bottom-up merges runs of width 1, then 2, then 4:

start:      25 41 29 37 10 14 13  6
width = 1:  25 41 | 29 37 | 10 14 |  6 13
width = 2:  25 29 37 41 | 6 10 13 14
width = 4:   6 10 13 14 25 29 37 41

Equal-length sorted runs tiling the whole array is unmistakable.

Top-down (the recursive version everyone writes) is depth-first, so mid-run it looks like this:

merged [0,4):  25 29 37 41 | 10 14 13  6

Left half fully sorted, right half still verbatim input.

Now the ambiguity, stated honestly. That top-down snapshot is identical to insertion sort's state after 3 steps. Sorted prefix, untouched suffix — both algorithms produce it, and no amount of staring resolves it. Two legitimate tie-breakers:

1. Prefix length. Merge sort's sorted prefix can only end on a recursive boundary: n/2, n/4, 3n/4. Insertion sort's grows by exactly one element per step, so a prefix of length 5 or 6 out of 8 rules merge sort out.
2. A sorted run in the right half. Top-down merge sort will, at some point, have a sorted block in the right half while the left is not yet sorted (see merged [4,8) in the trace). Insertion sort can never do that.

If a question genuinely admits both, say so and name the tie-breaker. Recognising an ambiguity and resolving it explicitly reads as stronger than picking one and hoping.

#include <iostream>
#include <vector>

// Lomuto partition: pivot = a[hi]. Returns the pivot's final index p.
// Guarantees a[lo..p-1] <= a[p] <= a[p+1..hi]; neither side is sorted.
int partition(std::vector<int>& a, int lo, int hi) {
    int pivot = a[hi];
    int i = lo - 1;                     // i = last index of the "<= pivot" block
    for (int j = lo; j < hi; ++j)
        if (a[j] <= pivot) std::swap(a[++i], a[j]);
    std::swap(a[i + 1], a[hi]);         // drop the pivot into its final slot
    return i + 1;
}

void quickSort(std::vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;               // 0 or 1 element: nothing to do
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
}

void merge(std::vector<int>& a, std::vector<int>& buf, int lo, int mid, int hi) {
    int i = lo, j = mid, k = lo;                      // [lo, mid) and [mid, hi)
    while (i < mid && j < hi)
        buf[k++] = (a[j] < a[i]) ? a[j++] : a[i++];   // '<' keeps it stable
    while (i < mid) buf[k++] = a[i++];
    while (j < hi)  buf[k++] = a[j++];
    for (int t = lo; t < hi; ++t) a[t] = buf[t];
}

void mergeSort(std::vector<int>& a, std::vector<int>& buf, int lo, int hi) {
    if (hi - lo <= 1) return;                         // 0 or 1 element
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, buf, lo, mid);
    mergeSort(a, buf, mid, hi);
    merge(a, buf, lo, mid, hi);
}

int main() {
    std::vector<int> a = {25, 41, 29, 37, 10, 14, 13, 6};
    std::swap(a[2], a[7]);                            // choose 29 as the pivot
    int p = partition(a, 0, static_cast<int>(a.size()) - 1);
    std::cout << "pivot at index " << p << ": ";
    for (int x : a) std::cout << x << ' ';
    std::cout << '\n';                 // 25 6 10 14 13 29 41 37, pivot index 5

    std::vector<int> b = {25, 41, 29, 37, 10, 14, 13, 6};
    std::vector<int> buf(b.size());
    mergeSort(b, buf, 0, static_cast<int>(b.size()));
    for (int x : b) std::cout << x << ' ';
    std::cout << '\n';                 // 6 10 13 14 25 29 37 41
    return 0;
}

The Big-O cheat sheet, with the reason attached

Do not memorise the table. Memorise the five shapes of work; the table then writes itself for code you have never seen.

Anchors that make log n concrete: log₂(1,000) ≈ 10, log₂(1,000,000) ≈ 20, log₂(1,000,000,000) ≈ 30. Binary search over a billion sorted items is thirty comparisons. This is why the O(n) vs O(log n) distinction is not academic.

The sorting comparison table — the "best" column is where the marks hide:

Things in that table people get wrong:

• Selection sort has no best case. Give it a perfectly sorted array and it still performs every one of the n(n−1)/2 comparisons, because the inner loop cannot know it has found the minimum without checking everything. It does, however, perform at most n−1 swaps — the fewest of any of these — which is its one genuine advantage when writes are expensive.
• Quicksort's worst case is triggered by sorted input when the pivot is the first or last element: every partition splits into 0 and n−1, giving n levels of O(n) work. Randomised or median-of-three pivots exist specifically to avoid this.
• Merge sort is the only one here with an O(n) space cost, and the only comparison sort in the table that is both stable and O(n log n) in the worst case.
• Comparisons and swaps are different metrics. Bubble sort does O(n²) of both; selection sort does O(n²) comparisons and O(n) swaps. If a question specifies one, answer that one.

Binary search: O(log n), but only on sorted data

Binary search is the payoff for sorting, and it has three things worth getting exactly right.

1. The precondition is not optional. On unsorted input, binary search does not crash and does not loop — it returns a confidently wrong answer. That is the worst failure mode a function can have. State the precondition in a comment.

2. The midpoint. Write it as low + (high - low) / 2, never (low + high) / 2. With int indices, low + high overflows once both pass roughly 1.07 billion:

INT_MAX          = 2147483647
low + high       = 1500000000 + 2000000000 = 3500000000   // overflows int (UB)
low + (high-low)/2 = 1750000000                            // always fine

Since high >= low inside the loop, high - low is non-negative and the addition can never exceed high. This exact bug sat undetected in widely-used standard libraries for years. In C++20 you can also write std::midpoint(low, high).

3. Pick one loop invariant and never mix. Two correct conventions exist:

Mixing them is the single most common source of infinite loops. In the inclusive form, writing high = mid instead of mid - 1 hangs: when high == low + 1, mid == low, and high = mid leaves the range unchanged forever.

Termination argument (worth one line if asked to prove correctness): mid always lies in [low, high], and both branches move a bound strictly past mid, so the range shrinks by at least one every iteration and roughly halves. From n to 1 takes ⌈log₂ n⌉ + 1 iterations.

When binary search is the wrong tool: for a single lookup on unsorted data, sorting first costs O(n log n) — far worse than one O(n) scan. Sorting pays off only across many queries (see Exercise 2). And if you never need ordering at all, a hash set gives O(1) average lookups and beats both.

The library already has all of this: std::binary_search for a yes/no answer, std::lower_bound for the insertion point, std::upper_bound, and std::equal_range. Write it by hand to show you can; call the library in real code.

#include <iostream>
#include <vector>

// Precondition: a is sorted ascending. Returns an index of target, or -1.
int binarySearch(const std::vector<int>& a, int target) {
    int low  = 0;
    int high = static_cast<int>(a.size()) - 1;   // signed! see the pitfalls below
    while (low <= high) {                        // <= : [low, high] is inclusive
        int mid = low + (high - low) / 2;        // never overflows
        if (a[mid] == target) return mid;
        if (a[mid] < target)  low  = mid + 1;    // discard left half AND mid
        else                  high = mid - 1;    // discard right half AND mid
    }
    return -1;
}

// First index i with a[i] >= target, or a.size() if none. Half-open [low, high).
int lowerBound(const std::vector<int>& a, int target) {
    int low = 0, high = static_cast<int>(a.size());
    while (low < high) {                         // < : high is one-past-the-end
        int mid = low + (high - low) / 2;
        if (a[mid] < target) low = mid + 1;
        else                 high = mid;         // NOT mid - 1: mid may be the answer
    }
    return low;
}

int main() {
    std::vector<int> a = {6, 10, 13, 14, 25, 29, 37, 41};
    std::cout << binarySearch(a, 25) << '\n';   // 4
    std::cout << binarySearch(a, 26) << '\n';   // -1  (absent)
    std::cout << lowerBound(a, 26)   << '\n';   // 5   (where 26 would go)
    std::cout << lowerBound(a, 42)   << '\n';   // 8   (past the end)
    return 0;
}

The mistakes people actually make

Reading the snapshot from the wrong end. Bubble builds at the tail, selection at the head. If you cannot keep them straight, remember that bubble sort's large values "rise" to the end, and selection sort selects the minimum and puts it at the front.

Assuming a sorted prefix means those elements are finished. Insertion sort's prefix is sorted but not final. If asked "how many elements are in their final position?", the honest answer for an insertion-sort snapshot is usually zero.

Off-by-one on the bubble inner bound. The condition must be j + 1 < n - pass. Writing j < n - pass makes the last comparison read a[n - pass], which on pass == 0 is a[n] — out of bounds. The + 1 exists because the loop body touches two adjacent cells.

Reversing the short-circuit in insertion sort. while (a[j] > key && j >= 0) evaluates a[j] before the bounds test. When key is the new minimum, j reaches -1 and you read a[-1]. It will usually not crash — it will quietly read adjacent memory, which is worse. && evaluates left to right and stops early, so the guard must come first.

Unsigned index types in binary search. size_t high = a.size() - 1; on an empty vector gives SIZE_MAX. And high = mid - 1 when mid == 0 wraps the same way. Verified failure: searching for a value smaller than everything in the array spins forever while reading out of bounds. Use signed indices for the inclusive form, or the half-open form where high = mid cannot underflow.

(low + high) / 2. Silent integer overflow on large arrays.

Failing to advance a bound. low = mid (instead of mid + 1) or high = mid inside an inclusive-range loop both produce infinite loops on inputs that stall on a two-element range. If your binary search hangs, this is almost always why.

Binary searching unsorted data. No error, no crash, just wrong answers. Also: sorting in order to do one search is slower than not sorting at all.

Claiming selection sort is O(n) on sorted input. It is not — see the table above.

Expecting a quicksort pivot to land in the middle. Partitioning gives one element its final position, nothing more. Balance is a probabilistic hope, not a guarantee, and the O(n²) worst case is exactly what happens when that hope fails.

Quoting an average case when the question asked for the worst. Quicksort is the trap: O(n log n) average, O(n²) worst. Merge sort and heapsort are O(n log n) in all cases. Read which one was asked for.

Exercises with solutions

Work through each question before opening the solution below it.

input: 25 41 29 37 10 14 13 6

(a) 25 10 14 13  6 | 29 37 41
(b)  6 10 13 | 37 41 14 29 25
(c) 10 14 25 29 37 41 | 13  6
(d) 25  6 10 14 13 | 29 | 41 37

m·n  >  n·log n + m·log n

m(n − log n) > n·log n
m > n·log n / (n − log n)

#include <algorithm>
#include <vector>

void answerQueries(std::vector<int>& data,
                   const std::vector<int>& queries,
                   std::vector<bool>& out) {
    std::sort(data.begin(), data.end());          // O(n log n), once
    out.resize(queries.size());
    for (std::size_t i = 0; i < queries.size(); ++i)
        out[i] = std::binary_search(data.begin(), data.end(), queries[i]);
}

int find(std::vector<int> a, int target) {
    size_t low = 0, high = a.size();
    while (low < high) {
        size_t mid = (low + high) / 2;
        if (a[mid] == target)     return mid;
        else if (a[mid] < target) low  = mid;
        else                      high = mid - 1;
    }
    return -1;
}

#include <vector>

// Precondition: a is sorted in ascending order.
// Returns an index of target, or -1 if absent.
int find(const std::vector<int>& a, int target) {
    int low  = 0;
    int high = static_cast<int>(a.size()) - 1;   // inclusive range
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target)  low  = mid + 1;
        else                  high = mid - 1;
    }
    return -1;
}

Related pages