Sorting Algorithms for Dummies

Because no single algorithm wins everywhere. Some are simple to write, some are fast on big data, some keep equal items in order (stable), some need extra memory, some don't. You pick the one that fits the job.

// ── The four properties you compare sorts on ────────
//
// 1. TIME — how many steps as the array grows.
//    Best  / Average / Worst  (Big O notation)
//
// 2. SPACE — extra memory needed besides the input.
//    "in-place"  → O(1) extra, sorts inside the original array.
//    "out-of-place" → needs an auxiliary array.
//
// 3. STABILITY — do equal elements keep their original order?
//    Sorting people by age — two 30-year-olds stay in the same
//    order they came in? That's "stable".
//
// 4. ADAPTIVE — does the algorithm go faster when the array
//    is already partly sorted?
//
// You'll see all four mentioned on every card below. ↓

Big O describes how the number of steps grows as the input grows. It doesn't measure seconds — it measures shape. For sorting n items, the common shapes are:

// n = number of items in the array
//
// O(n²)      — "quadratic"   . double the array, work goes 4×
//              Bubble, Selection, Insertion
//              Fine for n < 1,000. Slow for 1,000,000.
//
// O(n log n) — "linearithmic". double the array, work just over 2×
//              Merge, Quick, Heap
//              The gold standard for general-purpose sorting.
//
// O(n + k)   — "linear"       . work grows with array AND value range k.
//              Counting, Radix   (only for integers / bounded keys)
//              Fastest when k is small.
//
// O(log n)   — "logarithmic"  . each step halves the work
//              (you won't see this for SORTING, but for SEARCH a sorted array)
//
// Rule of thumb:
//   small array (n < ~50)        → Insertion Sort is genuinely fastest
//   general purpose, any data    → built-in Array.Sort (n log n)
//   only integers in a small range → Counting / Radix Sort (O(n))

Almost every sorting algorithm in this guide swaps two elements in an array. So let's define Swap once. In modern C# it's a single line thanks to tuple assignment.

// ── Swap two array slots in place ────────────────────
static void Swap(int[] a, int i, int j)
{
    (a[i], a[j]) = (a[j], a[i]);
    // Right-hand side is evaluated first, then assigned.
    // No temp variable needed in C# — the tuple does it for you.
}

// ── Example ──────────────────────────────────────────
int[] arr = [5, 2, 8, 1];
Swap(arr, 0, 2);
// arr is now [8, 2, 5, 1]

// In old-school code you'd write:
//   int tmp = a[i];
//   a[i] = a[j];
//   a[j] = tmp;
// Same result. The tuple version is just neater.

Picture bubbles rising in a glass of soda. After each full sweep across the array, the biggest unsorted value has floated all the way to the right. Do another sweep, the next biggest floats up. And so on. That's where the name comes from.

// ── The recipe (memorise this — everything else is detail) ──
//
//   1. Start at the left.
//   2. Look at arr[j] and arr[j+1].          ← a single pair
//   3. If they're in the wrong order, SWAP.
//   4. Move one slot right. Repeat 2–3.
//   5. When you reach the end, that's ONE PASS.
//      ☞ After pass 1, the LARGEST value is in its final spot.
//   6. Do another pass — one slot shorter than the last
//      (you don't need to look at the already-final tail).
//   7. If a whole pass made ZERO swaps, you're done. Stop.

Talk is cheap. Let's actually sort an array. Reading the trace top-to-bottom is the same as watching the algorithm run in slow motion.

Start:        3, 8, 1, 4

Pass 1:  3,8 ok       3, 8, 1, 4
         8,1 swap     3, 1, 8, 4
         8,4 swap     3, 1, 4, 8     ← 8 final

Pass 2:  3,1 swap     1, 3, 4, 8
         3,4 ok       1, 3, 4, 8     ← 4 final

Pass 3:  1,3 ok                      ← zero swaps, done!

Answer:  3 passes (the last is the empty-pass check),
         3 swaps total.

Here it is in C#. The numbered pins (1, 2, 3, 4) match the explanation right below the code — read them in order.

static void BubbleSort(int[] arr)
{
    int n = arr.Length;

    for (int i = 0; i < n - 1; i++)         1
    {
        bool swapped = false;               2

        for (int j = 0; j < n - 1 - i; j++) 3
        {
            if (arr[j] > arr[j + 1])
            {
                (arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
                swapped = true;
            }
        }

        if (!swapped) break;                4
    }
}

1. The pass counter — the metronome of the algorithm. Each tick of i is one full sweep. Why not n? Because after n − 1 biggest-values have surfed to the right, the smallest value is left at index 0 by pure elimination — no pass needed to "place" it. Trap: writing i <= n doesn't break the answer but does a guaranteed-useless extra pass.
2. The detector flag — a one-bit memory of "did anything move?" Reset every pass. Why not just measure passes? Because nearly-sorted input might finish in pass 2, not pass n − 1 — the flag catches this the instant it happens. Trap: declaring swapped outside the outer loop is the classic bug — once you set it true the first time, you've defeated the optimisation for the rest of the run.
3. The comparing loop — note the shrinking bound n − 1 − i. Every pass is one slot shorter than the last. Why not always go to n − 1? Because after pass i, the i largest values are already docked at the end — re-comparing them is pure waste. (Remember the Brain Power prompt above? This is the answer.) Trap: using j < n instead of j < n - 1 reads past the end of the array on the comparison arr[j] > arr[j+1] — guaranteed IndexOutOfRangeException.
4. The early exit — the line that earns Bubble Sort the word "adaptive". If a whole pass moved nothing, the array is sorted; stop. Why does this matter? Without it, an already-sorted array still costs O(n²); with it, O(n). One line, an entire order-of-magnitude. Trap: putting swapped = true in the wrong scope (see annotation 2) silently makes this if always-false-then-always-true — and you'd never notice in a code review unless you ran a benchmark on sorted input.

// ── Try it ───────────────────────────────────────────
int[] data = [5, 1, 4, 2, 8];
BubbleSort(data);
Console.WriteLine(string.Join(", ", data));
// → 1, 2, 4, 5, 8   ✓

The array gets split into two regions: a sorted prefix on the left (starts empty) and an unsorted suffix on the right. Each pass scans the suffix for its minimum and docks that value at the boundary.

// ── The recipe ───────────────────────────────────────
//
//   1. Boundary starts at index 0. Everything to the right is unsorted.
//   2. Scan the unsorted region. Remember the INDEX of the smallest value.
//   3. Swap that value with the element AT the boundary.
//      ☞ The boundary slot is now permanently correct.
//   4. Move the boundary one step right.
//   5. Repeat until the boundary reaches the last slot.
//      The final slot is automatically correct (only value left).
//
// Comparisons per pass:    n − 1, n − 2, n − 3, … 1    →  ~n²/2 total
// Swaps total:             at most n − 1 (one per pass, often skipped)
//
// Insight: comparisons don't shrink with how sorted the data is.
//          Selection Sort does the EXACT SAME WORK every time —
//          it's NOT adaptive. Bubble Sort with the flag is.

Each row = one full scan. Green cells are docked (final). Orange = current minimum being shuttled to the front.

Start:         5, 2, 4, 1, 3

Pass 1: min = 1 (idx 3). Swap with idx 0.
   →           1, 2, 4, 5, 3        (swap #1)

Pass 2: min in {2,4,5,3} = 2 (idx 1). Already there.
   →           1, 2, 4, 5, 3        (no swap)

Pass 3: min in {4,5,3} = 3 (idx 4). Swap with idx 2.
   →           1, 2, 3, 5, 4        (swap #2)

Pass 4: min in {5,4} = 4 (idx 4). Swap with idx 3.
   →           1, 2, 3, 4, 5        (swap #3)

Answer:  3 swaps out of a possible 4.
         (Pass 2's "min is already in place" check saved one.)

Same skeleton as Bubble Sort — outer loop + inner loop — but the inner loop is a scan, not a compare-and-swap. Read the pins.

static void SelectionSort(int[] arr)
{
    int n = arr.Length;

    for (int i = 0; i < n - 1; i++)                1
    {
        int minIndex = i;                          2

        for (int j = i + 1; j < n; j++)            3
        {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }

        if (minIndex != i)                         4
            (arr[i], arr[minIndex]) = (arr[minIndex], arr[i]);
    }
}

1. The boundary cursor. i is the index of the next slot to dock. We stop at n − 1 because the final slot self-resolves. Why not n? Because by the time the unsorted region has one element, that element is automatically the minimum — no pass needed. Trap: running to n isn't wrong, but you'll waste a comparison-less iteration. Aesthetic, not correctness.
2. The "min so far" pointer. Start by assuming the boundary itself holds the smallest — then prove yourself wrong. Why an index and not a value? Because you need the location to swap. Storing the value would force a second scan to find it. Trap: resetting minIndex outside the outer loop turns a sort into "find the global minimum and put it at slot 0 forever" — a single-pass nothing.
3. The scan — note j = i + 1. Start one past the boundary, because slot i is already the candidate. Why not j = i? You'd compare minIndex against itself on the first iteration — harmless but wasteful. Why < and not <=? Strict less-than makes the sort behave as if it were stable on the comparison side — though the swap on line 4 still breaks stability. (See the trap below.)
4. The conditional swap. Only swap if you found a smaller value somewhere down the array. Why bother with the if? An unconditional swap costs ~3 writes; skipping it when the min is already in place saves work — especially on flash storage where writes wear the device. Trap: removing the if doesn't change correctness, but on already-sorted input you go from 0 writes to 3 × (n − 1) writes — a silent perf regression.

// ── Try it ───────────────────────────────────────────
int[] data = [64, 25, 12, 22, 11];
SelectionSort(data);
Console.WriteLine(string.Join(", ", data));
// → 11, 12, 22, 25, 64   ✓ (3 actual swaps, 10 comparisons)

Same two-region split as Selection Sort: sorted prefix on the left, unsorted suffix on the right. But you don't find anything — you insert. Each pass takes the next unsorted value and shuffles it left until it finds its home.

// ── The recipe ───────────────────────────────────────
//
//   1. The first element is "a sorted list of 1" by definition. Skip it.
//   2. KEY = the next unsorted value (at index i).
//   3. Walk LEFT from index i − 1:
//        • If the value to the left is bigger than KEY, shift it RIGHT.
//        • Stop when the value to the left is ≤ KEY (or you fall off slot 0).
//   4. Drop KEY into the empty slot you just created.
//   5. Repeat with the next element. The sorted region grows by 1.
//
// Time per pass:
//   • Best  (already sorted):  1 comparison.   Total: O(n).
//   • Worst (reverse sorted):  i comparisons.  Total: O(n²).
//
// ☞ This is the FIRST sort in the guide that's actually adaptive
//   in a meaningful way — and the reason it's the workhorse for
//   small / nearly-sorted inputs everywhere.

Each row = the array after inserting the next KEY. Orange = the KEY being placed. Green = the growing sorted prefix.

(a)  [1, 2, 3, 4, 5]   — already sorted
     KEY=2: 1 ≤ 2, no shifts
     KEY=3: 2 ≤ 3, no shifts
     KEY=4: 3 ≤ 4, no shifts
     KEY=5: 4 ≤ 5, no shifts
     ────────────────────────
     Total: 0 shifts. O(n) — best case.

(b)  [5, 4, 3, 2, 1]   — reverse sorted
     KEY=4: shift 5             → 1 shift
     KEY=3: shift 5, 4          → 2 shifts
     KEY=2: shift 5, 4, 3       → 3 shifts
     KEY=1: shift 5, 4, 3, 2    → 4 shifts
     ────────────────────────
     Total: 10 shifts = n(n-1)/2. O(n²) — worst case.

The 0-vs-10 gap on the same n is exactly what
"strongly adaptive" looks like in numbers.

Note: the inner loop is a while, not a for — because we don't know how many shifts each KEY will need. We stop the moment we find the right spot.

static void InsertionSort(int[] arr)
{
    for (int i = 1; i < arr.Length; i++)        1
    {
        int key = arr[i];                       2
        int j   = i - 1;

        while (j >= 0 && arr[j] > key)          3
        {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;                       4
    }
}

1. Outer loop starts at i = 1, not 0. The element at index 0 is, by definition, "a sorted list of size 1". Why not 0? KEY at index 0 would do nothing — j starts at -1, the while never runs, the value gets put back where it was. Harmless but wasteful. Trap: mixing this up with Selection Sort's i < n - 1 bound — Insertion needs to reach the last element to insert it.
2. Save the KEY before the shifts start. Critical. The shifts are about to overwrite the slot KEY currently lives in — if you don't snapshot the value first, it's gone. Why not just arr[j + 1] at the end? Because by then, that slot has been overwritten by a shifted value. KEY only exists in this local int. Trap: forgetting to save and then reading arr[i] later — silent data corruption that passes most small test cases.
3. The shift loop — note the short-circuit j >= 0 &&. Both conditions must hold. Why the bounds check first? Because C# evaluates left-to-right and short-circuits. If j falls below 0, the arr[j] read would throw — putting the cheap check first prevents that. Trap: swapping the operand order (arr[j] > key && j >= 0) compiles fine but throws IndexOutOfRangeException the moment KEY needs to be inserted at index 0.
4. Drop KEY into the gap at j + 1, not j. When the while exits, j is pointing at the value that's smaller than (or equal to) KEY — KEY belongs one slot to its right. Why + 1? The shift moved each arr[j] into arr[j + 1], leaving arr[j + 1] as the empty gap to fill. Trap: writing arr[j] = key instead — you'll overwrite the value KEY was supposed to land in front of, breaking the sort silently.

// ── Try it ───────────────────────────────────────────
int[] data = [5, 2, 4, 6, 1, 3];
InsertionSort(data);
Console.WriteLine(string.Join(", ", data));
// → 1, 2, 3, 4, 5, 6   ✓

Merge Sort is two simple ideas stacked. Master both and you've mastered the algorithm — and a third of the algorithms book you'll read later.

// ── Idea #1 — DIVIDE & CONQUER ───────────────────────
//
//   "I don't know how to sort 1,000,000 things.
//    I DO know how to sort 1 thing — it's already sorted.
//    So I'll split until everything's a 1-thing pile, and
//    then I only need to know how to MERGE."
//
//   This is a pattern, not just an algorithm:
//   binary search, FFT, the closest-pair problem, parallel
//   reduce — same shape.

// ── Idea #2 — MERGING TWO SORTED LISTS ───────────────
//
//   Given two sorted lists, you can produce one sorted list
//   in O(n + m) time using TWO POINTERS:
//
//     Left:  [1, 4, 8]      Right: [2, 5, 7]
//
//     1 vs 2  → take 1  → [1]
//     4 vs 2  → take 2  → [1, 2]
//     4 vs 5  → take 4  → [1, 2, 4]
//     8 vs 5  → take 5  → [1, 2, 4, 5]
//     8 vs 7  → take 7  → [1, 2, 4, 5, 7]
//     right done — drain left → [1, 2, 4, 5, 7, 8]
//
//   That's the whole merge step. Two pointers, one comparison
//   per slot of output. Try writing it from scratch — it's
//   shorter than your typical for loop.

Read the diagram top → bottom (the split phase), then bottom → top (the merge phase). The split phase is "logically" recursive — no real work happens until the leaves.

// ── Split phase (top → bottom) ───────────────────────
//                  [38, 27, 43, 3, 9, 82, 10]
//                 ╱                            ╲
//          [38, 27, 43, 3]                 [9, 82, 10]
//           ╱          ╲                    ╱        ╲
//       [38, 27]      [43, 3]            [9, 82]    [10]
//        ╱    ╲        ╱    ╲             ╱   ╲
//     [38]   [27]   [43]   [3]          [9]  [82]
//
//   Leaves are 1-element — sorted by definition.

// ── Merge phase (bottom → top) ───────────────────────
//     [27, 38]      [3, 43]            [9, 82]    [10]
//          ╲           ╱                   ╲       ╱
//        [3, 27, 38, 43]                 [9, 10, 82]
//                       ╲              ╱
//              [3, 9, 10, 27, 38, 43, 82]   ← sorted!
//
//   3 levels of splitting (log₂ 7 ≈ 3),
//   each level merges 7 elements total
//   → 21 operations, ~7 × 3, ≈ n log n.   ✓

L = [1, 4, 8, 9]      R = [2, 3, 5, 7]
i=0                    j=0

L[0]=1 vs R[0]=2 → take 1 (i→1)        out: [1]
L[1]=4 vs R[0]=2 → take 2 (j→1)        out: [1, 2]
L[1]=4 vs R[1]=3 → take 3 (j→2)        out: [1, 2, 3]
L[1]=4 vs R[2]=5 → take 4 (i→2)        out: [1, 2, 3, 4]
L[2]=8 vs R[2]=5 → take 5 (j→3)        out: [1, 2, 3, 4, 5]
L[2]=8 vs R[3]=7 → take 7 (j→4)        out: [1, 2, 3, 4, 5, 7]
R exhausted — drain L → 8, 9
                                       out: [1, 2, 3, 4, 5, 7, 8, 9]

8 elements, 6 comparisons + 2 drained = O(n + m).

Two methods. MergeSort is the recursive shell (split). Merge is where the actual work happens (combine two sorted runs). Read the pins on each.

static void MergeSort(int[] arr, int lo, int hi)
{
    if (lo >= hi) return;                       1

    int mid = lo + (hi - lo) / 2;               2
    MergeSort(arr, lo, mid);
    MergeSort(arr, mid + 1, hi);
    Merge(arr, lo, mid, hi);
}

static void Merge(int[] arr, int lo, int mid, int hi)
{
    int[] left  = arr[lo..(mid + 1)];           3
    int[] right = arr[(mid + 1)..(hi + 1)];

    int i = 0, j = 0, k = lo;

    while (i < left.Length && j < right.Length)
    {
        arr[k++] = left[i] <= right[j]          4
            ? left[i++]
            : right[j++];
    }

    while (i < left.Length)  arr[k++] = left[i++];   5
    while (j < right.Length) arr[k++] = right[j++];
}

1. The recursion base case. When lo >= hi we have 0 or 1 element — already sorted. Why not lo == hi? Because of safety: in some corruption paths or off-by-one bugs lo > hi can happen, and a strict == would skip the bounce-out, recurse infinitely, and stack-overflow. Trap: writing lo > hi alone misses the lo == hi case and you'll recurse into a single-element sub-array forever.
2. The mid-point — written this way on purpose. lo + (hi - lo) / 2 is identical to (lo + hi) / 2 mathematically but cannot overflow. Why does that matter? When lo and hi are both large (close to int.MaxValue in production code that sorts huge arrays), lo + hi wraps around to a negative number and your index goes off into nowhere. Trap: the famous "binary search bug" Jon Bentley wrote about in 2006 — sat undetected in the JDK for decades. Same fix applies here.
3. Two temporary arrays — the cost of stability and simplicity. Merge needs the left and right halves untouched while it writes back into arr. Copying them out is the cleanest way. Why not merge in place? You can, but it's surprisingly hard (look up "in-place merge sort") and usually slower than the simple version. Trap: trying to "save memory" by reading from arr directly during the merge — you'll overwrite values you haven't merged yet. Use the temp arrays.
4. The stability switch — <=, not <. When left and right have equal values, taking from left first preserves the original order. Why does this matter? When you sort objects by a secondary key after already sorting by a primary, stability is what keeps the primary sort intact. Trap: "optimising" to strict < looks innocent and breaks every stable-sort guarantee in your codebase. The Brain Power above is asking exactly this.
5. The two drain loops. When one half is exhausted, the other half's remaining values are already in order — just copy them in. Why two separate loops instead of one? Because only one of them ever runs (the half with elements left). Combining them needs an extra branch in the hot loop, which is slower. Trap: forgetting one of these silently truncates the output — you'd lose the tail of either left or right.

// ── Try it ───────────────────────────────────────────
int[] data = [38, 27, 43, 3, 9, 82, 10];
MergeSort(data, 0, data.Length - 1);
Console.WriteLine(string.Join(", ", data));
// → 3, 9, 10, 27, 38, 43, 82   ✓

Same divide-and-conquer skeleton as Merge Sort, but smarter splitting. Instead of cutting blindly in the middle and merging at the end, Quick Sort uses a single rearrangement to put every element on the correct side of the pivot. Both halves can then be sorted independently — no merge step needed.

// ── The recipe ───────────────────────────────────────
//
//   1. PICK a PIVOT from the array.
//      Naive: last element. Smart: median-of-three or random.
//
//   2. PARTITION the array around the pivot:
//        everything <= pivot  →  goes LEFT
//        the pivot              →  sits in the MIDDLE (final position!)
//        everything >  pivot  →  goes RIGHT
//
//   3. RECURSE on the left sub-array.
//      RECURSE on the right sub-array.
//      Don't recurse on the pivot — it's already done.
//
//   4. Base case: sub-arrays of size 0 or 1 are done.

// ── Why pivot choice is everything ───────────────────
//
//   GOOD pivot (median):
//     splits the array roughly 50/50
//     recursion depth ≈ log n
//     total work ≈ n log n   ←  best case scenario
//
//   BAD pivot (max or min):
//     one side empty, other side has n − 1
//     recursion depth ≈ n
//     total work ≈ n²        ←  pathological
//
//   Naive Quick Sort + sorted input = the canonical example
//   of "looked fine in tests, exploded in production."

Lomuto scheme: pivot = last element. The dark-bordered cell is the pivot. Green = sub-array that's already final. We'll only show the first partition step in detail, then the recursive results.

// ── Recursion tree on this run ───────────────────────
//
//                [7,2,1,8,6,3,5,4]    pivot 4 → final pos 3
//                ╱                ╲
//          [2,1,3]              [6,8,5,7]
//          pivot 3              pivot 7
//          ╱     ╲              ╱       ╲
//       [2,1]   []           [6,5]      [8]
//       pivot 1                pivot 5
//        ╱  ╲                  ╱   ╲
//      []   [2]              []    [6]
//
//   Depth ≈ log₂ 8 = 3 ✓
//   On a SORTED input, the same algorithm makes
//   depth = 8 → O(n²). That's the temper.

arr = [3, 8, 1, 5, 2]      pivot = 2,   i = -1

j=0: arr[0]=3, 3 > 2, skip                arr = [3, 8, 1, 5, 2]
j=1: arr[1]=8, 8 > 2, skip                arr = [3, 8, 1, 5, 2]
j=2: arr[2]=1, 1 ≤ 2 → i=0, swap 0↔2      arr = [1, 8, 3, 5, 2]
j=3: arr[3]=5, 5 > 2, skip                arr = [1, 8, 3, 5, 2]

End of loop, swap pivot to slot i+1 = 1   arr = [1, 2, 3, 5, 8]

Pivot 2 lands at index 1. ✓
Left = [1] (size 1, done). Right = [3, 5, 8] (recurse).

Two methods. QuickSort = recursive shell. Partition = the real algorithm. The trick of Lomuto: i tracks the boundary of "things <= pivot seen so far".

static void QuickSort(int[] arr, int lo, int hi)
{
    if (lo >= hi) return;                            1

    int p = Partition(arr, lo, hi);
    QuickSort(arr, lo, p - 1);
    QuickSort(arr, p + 1, hi);                       2
}

static int Partition(int[] arr, int lo, int hi)
{
    int pivot = arr[hi];                             3
    int i = lo - 1;                                  4

    for (int j = lo; j < hi; j++)
    {
        if (arr[j] <= pivot)
        {
            i++;
            (arr[i], arr[j]) = (arr[j], arr[i]);     5
        }
    }

    (arr[i + 1], arr[hi]) = (arr[hi], arr[i + 1]);   6
    return i + 1;
}

1. The base case. Sub-arrays of 0 or 1 are sorted. Why >= not ==? Sub-arrays of size 0 happen naturally — when the pivot was the smallest or largest value, one side of the partition is empty (p − 1 < lo or p + 1 > hi). Strict equality misses these. Trap: lo == hi alone causes infinite recursion on empty sub-arrays.
2. Critically: don't recurse over the pivot. The pivot is at index p and already in its final sorted position. Recursing on (lo, p) instead of (lo, p - 1) wastes work and breaks the algorithm's guarantee. Trap: off-by-one here is the #1 Quick Sort bug — produces wrong output on inputs with duplicates.
3. Pivot = last element — naive but legible. Production code never does this. Why? Already-sorted input degrades to O(n²) (see the Brain Power). How to fix: use median-of-three (arr[lo], arr[mid], arr[hi] — pick the middle one) or random pivot (swap arr[hi] with a random index before partitioning). Both fix the worst case.
4. The boundary pointer starts at lo − 1. It represents "the last index that's known to be ≤ pivot." Starts before the sub-array because we haven't seen any small values yet. Why not lo? Because that would imply arr[lo] is already known small — but we haven't checked it. Starting at lo − 1 means i + 1 is always the next empty "small region" slot.
5. The partition swap. When we find a value <= pivot, increment i and swap it into the small region. Why <= not <? So that values equal to the pivot land on the left side. Mixed sides break the recursion balance on duplicate-heavy inputs. Trap: < instead of <= creates a bizarre worst case on arrays of all identical values — they all go right, partition produces an empty left, recursion depth = n, performance dies.
6. Final swap — pivot to its sorted position. The pivot has been sitting at arr[hi] the whole time. After the loop, i + 1 is the first "> pivot" slot. Swap the pivot there. Why i + 1 not i? Because i is the last small index — the pivot belongs just past the small region, not inside it. Trap: swapping with arr[i] moves a value <= pivot to the end and the pivot lands in the wrong half — algorithm silently produces unsorted output.

// ── Try it ───────────────────────────────────────────
int[] data = [7, 2, 1, 8, 6, 3, 5, 4];
QuickSort(data, 0, data.Length - 1);
Console.WriteLine(string.Join(", ", data));
// → 1, 2, 3, 4, 5, 6, 7, 8   ✓

// In production: just call Array.Sort(data). It's IntroSort,
// it's faster than your handwritten Quick Sort, and it's
// algorithmic-complexity-attack-resistant.

A heap is a binary tree stored in an array, where every parent is ≥ both its children (a max-heap). The root is always the maximum. Take the root, swap it to the end, restore the heap, repeat. Two for-loops, no recursion, in-place, guaranteed O(n log n). In .NET this same data structure powers PriorityQueue<T, K>.

// ── The recipe ───────────────────────────────────────
//
//   Phase 1 — BUILD a max-heap from the input.    O(n)
//             (Yes, only n. Surprising. Proof in references.)
//
//   Phase 2 — Repeatedly do:
//             • swap root (max) with the last unsorted slot
//             • the array now has [..., max] sorted at the end
//             • shrink the "heap region" by one
//             • re-heapify the root to restore the property
//             That's O(log n) per iteration, n iterations → O(n log n)

// ── Heap-as-array — the secret weapon ────────────────
//
//   Heap stored as an array, NOT a tree of nodes:
//
//     index:    0  1  2  3  4  5  6
//     value:  [16 14 10  8  7  9  3]    ← max-heap
//
//   For any index i:
//     parent(i) = (i - 1) / 2
//     left(i)   = 2*i + 1
//     right(i)  = 2*i + 2
//
//   No pointers. No allocations. Cache-friendly.
//   This is why heaps are the right way to ship priority queues.

static void HeapSort(int[] arr)
{
    int n = arr.Length;

    // Phase 1: build max-heap from the bottom up.
    for (int i = n / 2 - 1; i >= 0; i--)         1
        Heapify(arr, n, i);

    // Phase 2: extract max one at a time.
    for (int i = n - 1; i > 0; i--)
    {
        (arr[0], arr[i]) = (arr[i], arr[0]);     2
        Heapify(arr, i, 0);                      3
    }
}

// "Sift-down" — restore the max-heap property at `root`.
static void Heapify(int[] arr, int heapSize, int root)
{
    int largest = root;
    int left  = 2 * root + 1;
    int right = 2 * root + 2;

    if (left  < heapSize && arr[left]  > arr[largest]) largest = left;
    if (right < heapSize && arr[right] > arr[largest]) largest = right;

    if (largest != root)                         4
    {
        (arr[root], arr[largest]) = (arr[largest], arr[root]);
        Heapify(arr, heapSize, largest);
    }
}

1. Start at the last non-leaf and walk backwards. Index n/2 − 1 is the deepest internal node. Why backwards? So that when we heapify a node, its children's subtrees are already heaps — that's what makes a single sift-down sufficient. Trap: starting at index 0 (top-down) doesn't build a valid heap and costs O(n log n) instead of O(n).
2. Move the max (root) to the end of the unsorted region. The root is the current maximum; the last slot of the heap region is its final sorted home. Why i > 0 not i >= 0? When only one element is left it's already in place — no swap needed. Trap: i >= 0 still works but does one wasted heapify on an empty heap.
3. Re-heapify with the SHRUNK size i. The freshly-placed max at index i is now outside the heap region — passing i (not n) is what keeps the algorithm in-place. Trap: passing n would re-include the sorted suffix, destroying both the heap and the sort order.
4. Recurse only if something actually moved. If the root was already the largest, the subtree is already a heap. Why bother with the check? Avoids meaningless recursion that does no work. Trap: not having the check is correct but burns stack frames — and the recursion can be replaced by a while-loop in production code to make it iterative.

Counting Sort doesn't compare values. It uses them — as indices into a counting array. If you know the value range up front and the range is small, this beats every comparison sort: O(n) flat. The catch is in the words "if you know" and "small".

// ── The recipe ───────────────────────────────────────
//
//   You want to sort ages of 1,000 employees. Ages are 0–120.
//
//   1. Allocate count[121] = all zeros.
//   2. For every input value v:   count[v]++
//      Now count[v] = how many times v appeared.
//   3. PREFIX-SUM the counts left-to-right:
//      count[i] = number of values <= i
//                = "where does the LAST occurrence of i go in output?"
//   4. Walk the input IN REVERSE. For each value v:
//      output[--count[v]] = v
//      (Reverse walk is what keeps the sort stable.)
//
//   Total: 3 linear passes. O(n + k) time, O(n + k) space.

// ── Example: [4, 2, 2, 8, 3, 3, 1]  k = 8 ────────────
//
//   Phase 1: count = [0, 1, 2, 2, 1, 0, 0, 0, 1]
//                         ↑     ↑   ↑           ↑
//                       one 1  two 3's          one 8
//
//   Phase 2: prefix sum → [0, 1, 3, 5, 6, 6, 6, 6, 7]
//                                  ↑  ↑           ↑
//                       3 ≤ 3      ≤ 4            ≤ 8
//
//   Phase 3: walk input in reverse, drop into output
//      → output = [1, 2, 2, 3, 3, 4, 8]   ✓ sorted, stable.

static int[] CountingSort(int[] arr, int maxVal)
{
    int[] count  = new int[maxVal + 1];           1
    int[] output = new int[arr.Length];

    foreach (int x in arr) count[x]++;            2

    for (int i = 1; i <= maxVal; i++)             3
        count[i] += count[i - 1];

    for (int i = arr.Length - 1; i >= 0; i--)     4
        output[--count[arr[i]]] = arr[i];

    return output;
}

1. Count array sized for the value range, not the input. If max value is 120, allocate int[121]. Why size by k and not n? Because the index into count is the value itself — slots not corresponding to actual values stay zero. Trap: sizing it by arr.Length instead of maxVal + 1 means values larger than n explode with IndexOutOfRangeException.
2. Count occurrences — a single pass. Use each value as the index. Why foreach instead of for? Negligible difference here; both are O(n). I prefer foreach for clarity since we never need the index. Trap: negative values throw — handle with an offset.
3. Prefix sum — converts "count" into "ending position". After this, count[v] − 1 is the index in output where the last occurrence of v belongs. Why a separate loop? Because phase 4 needs all counts finalised. Combining phase 2 and 3 in one loop produces wrong totals. Trap: off-by-one with i <= maxVal vs i < maxVal — the count array has maxVal + 1 slots, so <= is correct.
4. Reverse walk + decrement = stable output. --count[arr[i]] reserves a slot and immediately writes into it. Decrementing makes the next occurrence of the same value land in the previous slot. Why reverse? Walking forward would put the first input value at the last output slot for ties — order flipped. Trap: count[arr[i]]-- (postfix on the index expression) computes the slot then decrements — same effect here but easier to get wrong elsewhere.

If the value range is too big for Counting Sort to allocate (think 32-bit integers, ID numbers, sortable strings), Radix Sort works around it. Sort by the least-significant digit first using a stable Counting Sort, then by the next digit, then the next. After d passes — where d = number of digits — the array is sorted. Linear time per pass, d passes, O(d · n) total.

// ── Example trace ────────────────────────────────────
//
//   Start:       170, 45, 75, 90, 802, 24, 2, 66
//
//   By 1s digit  → 170, 90, 802, 2, 24, 45, 75, 66
//                  ones: 0   0   2  2   4   5   5   6
//
//   By 10s digit → 802, 2, 24, 45, 66, 170, 75, 90
//                  tens: 0   0  2   4   6   7    7   9
//
//   By 100s digit → 2, 24, 45, 66, 75, 90, 170, 802
//                  hundreds: 0  0   0   0   0   0   1    8
//
//   Sorted!  Each pass = one stable Counting Sort.
//
// ── Why does this work? ──────────────────────────────
//
//   Because each pass is STABLE, the order from previous passes
//   is preserved within each digit bucket. So after sorting by 10s,
//   numbers with the same 10s digit are still in 1s-digit order.
//   After sorting by 100s, same logic on the 100s bucket.
//
//   Read each row carefully — that's the whole proof.

static int[] RadixSort(int[] arr)
{
    int max = arr.Max();                                1

    for (int exp = 1; max / exp > 0; exp *= 10)         2
        arr = CountingSortByDigit(arr, exp);

    return arr;
}

static int[] CountingSortByDigit(int[] arr, int exp)
{
    int[] output = new int[arr.Length];
    int[] count  = new int[10];                         3

    foreach (int x in arr) count[(x / exp) % 10]++;     4
    for (int i = 1; i < 10; i++) count[i] += count[i - 1];

    for (int i = arr.Length - 1; i >= 0; i--)
    {
        int digit = (arr[i] / exp) % 10;
        output[--count[digit]] = arr[i];
    }
    return output;
}

1. Find the max — it tells you when to stop. Number of digits in max = number of passes needed. Why not pick a fixed number? If all your data is small (3-digit ID codes), running 10 passes is pure waste. Trap: empty arrays — arr.Max() throws on those. Add an early return.
2. The loop is unusual: by powers of 10. exp jumps 1, 10, 100, 1000… Why max / exp > 0? Because once exp exceeds max, all digits at that place are 0 — no more sorting needed. Trap: running while exp <= max wastes one extra pass. Using != 0 instead of > 0 is fine for positive values but breaks if you ever extend to negatives.
3. 10 buckets — one per digit. Base 10 means digits are 0–9. Why not base 256? You can. Sorting 32-bit integers in base 256 = 4 passes total (vs 10 for base 10). Production radix sorts use base 256 or higher. Trap: mistakenly sizing count by arr.Length — index goes 0–9 regardless of input size.
4. Extract the digit: (x / exp) % 10. Divide by exp to right-shift past the lower digits, mod 10 to grab the rightmost remaining. Why not bit-shifts? For base 10 you need division; for base 256 (or any power of 2), bit-shifts ((x >> shift) & 0xFF) are vastly faster. That's how production radix sorts get their speed. Trap: negative numbers — % in C# returns the sign of the dividend, so digits go negative. Handle with offset or two-pass (negatives, then positives).

Eight sorts, one table. Memorise this and you can answer 90% of "which sort?" questions on the fly. n = items, k = value range, d = digits, b = base (10 for decimal radix).

// Algorithm     | Best       | Average    | Worst      | Space    | Stable | In-place | Adaptive
// --------------+------------+------------+------------+----------+--------+----------+----------
// Bubble        | O(n)       | O(n²)      | O(n²)      | O(1)     | YES    | YES      | YES
// Selection     | O(n²)      | O(n²)      | O(n²)      | O(1)     | NO     | YES      | NO
// Insertion     | O(n)       | O(n²)      | O(n²)      | O(1)     | YES    | YES      | YES ★★★
// Merge         | O(n log n) | O(n log n) | O(n log n) | O(n)     | YES    | NO       | NO
// Quick         | O(n log n) | O(n log n) | O(n²)      | O(log n) | NO     | YES      | NO
// Heap          | O(n log n) | O(n log n) | O(n log n) | O(1)     | NO     | YES      | NO
// Counting      | O(n + k)   | O(n + k)   | O(n + k)   | O(n + k) | YES    | NO       | NO
// Radix (LSD)   | O(d·(n+b)) | O(d·(n+b)) | O(d·(n+b)) | O(n + b) | YES    | NO       | NO

// ── Reading the table in 30 seconds ──────────────────
//
//   STABILITY    — preserves order of equal items? Critical when
//                  sorting by a secondary key after a primary.
//   IN-PLACE     — sorts inside the input, no auxiliary array.
//                  Matters when memory is tight or O(n) extra is a no-go.
//   ADAPTIVE     — faster on already-sorted or nearly-sorted input?
//                  Insertion Sort is the king here.
//
// ── The 5 sentences that summarise everything ────────
//
//   1. Comparison-based sorts can't go below O(n log n) in the worst case.
//   2. Counting and Radix sidestep that by NOT comparing.
//   3. Quick is fastest in practice; Merge is fastest with a guarantee.
//   4. Insertion is fastest for small n and almost-sorted data.
//   5. Heap is the safety net — guaranteed O(n log n) in-place.

Walk the tree top-down. Answer "yes" or "no" at each node. Most real-world problems land at one of the first three leaves.

Is your data in a .NET collection?
│
├─ YES → does order of EQUAL items matter (stability)?
│        │
│        ├─ YES → LINQ .OrderBy(...).ThenBy(...)       ← stable Merge
│        │
│        └─ NO  → Array.Sort  /  List<T>.Sort         ← IntroSort
│
└─ NO (you're rolling your own — interview, embedded, custom data)
   │
   ├─ Is n < ~16?
   │   └─ YES → Insertion Sort                        ← simplest, fast
   │
   ├─ Is the data almost-sorted (streaming inserts)?
   │   └─ YES → Insertion Sort                        ← strongly adaptive
   │
   ├─ Are the values integers with range < n · log n?
   │   └─ YES → Counting Sort                         ← linear
   │
   ├─ Are the values integers in a HUGE range (or fixed-width strings)?
   │   └─ YES → Radix Sort                            ← linear
   │
   ├─ Need GUARANTEED O(n log n) and stability?
   │   └─ YES → Merge Sort                            ← safe
   │
   ├─ Need GUARANTEED O(n log n) but in-place?
   │   └─ YES → Heap Sort                             ← steady
   │
   └─ Otherwise (the 80% case)
       └─ Quick Sort with median-of-three pivot       ← fastest in practice

// ── The interview shortcut ───────────────────────────
// 1. Ask: "what's n? what's the value range? do duplicates matter?"
// 2. Match the answers against the tree.
// 3. State your choice + WHY.
// Interviewers don't grade you on the algorithm — they grade you on the WHY.

In real code you almost never roll your own sort — and you shouldn't. The runtime is smarter than you. Here's exactly what each call does under the hood, in 2025-vintage .NET.

// ── Array.Sort / List<T>.Sort — IntroSort hybrid ─────
//
//   For primitive types (int, long, etc.):
//     1. Quick Sort with median-of-three pivot.
//     2. If recursion depth exceeds 2 · log₂(n) → switch to Heap Sort
//        (guarantees O(n log n) even on adversarial input).
//     3. For sub-arrays of size ≤ 16 → Insertion Sort.
//
//   Result: NOT STABLE, but the fastest general-purpose
//   in-place sort the runtime can offer.
int[] nums = [5, 1, 4, 2, 8, 3];
Array.Sort(nums);                                       // ≈ best in class for primitives

// ── LINQ OrderBy / OrderByDescending — stable Merge ──
//
//   • Uses a stable Merge-like algorithm internally.
//   • Allocates a working buffer of n.
//   • ThenBy/ThenByDescending chain into a composite comparer
//     — total sort, NOT a re-sort per call.
//   • Deferred execution: nothing sorts until you enumerate.
var sorted = orders
    .OrderBy(o => o.Date)            // primary key
    .ThenBy(o => o.Total)            // secondary key  (stability preserves date order)
    .ToList();                       // ← THIS is when the sort runs

// ── Span<T>.Sort — zero-allocation primitive sort ────
//
//   Same algorithm as Array.Sort, but operates on a span —
//   useful inside hot paths where you can't allocate.
Span<int> span = stackalloc int[] { 5, 2, 8, 1, 9, 3 };
span.Sort();                                            // sorts in place, no GC pressure

// ── PriorityQueue<TElement, TPriority> — the heap ────
//
//   Added in .NET 6. Backed by a binary min-heap.
//   THIS is what you actually want when "I need the smallest first"
//   — not a sort, a priority queue.
var pq = new PriorityQueue<string, int>();
pq.Enqueue("low",    5);
pq.Enqueue("urgent", 1);
pq.Enqueue("medium", 3);

while (pq.Count > 0)
    Console.WriteLine(pq.Dequeue());
//  → urgent, medium, low   (O(log n) per enqueue/dequeue)

// ── The performance table (rough, m1-pro, .NET 8) ────
//
//   n = 1,000,000 random ints:
//     Array.Sort                ~  35 ms
//     Insertion (hand-written)  ~ 600,000 ms   (don't try this at home)
//     Hand-written QuickSort    ~  60 ms       (no JIT-tuned IntroSort tricks)
//     LINQ OrderBy → ToArray    ~ 110 ms       (extra allocations)
//     Counting Sort (k=1000)    ~  12 ms       (when applicable, wow)
//     Radix Sort (4 passes)     ~  25 ms       (faster than Array.Sort!)
//
//   You will not beat Array.Sort by writing your own Quick Sort.
//   The only sorts that beat it are problem-specific (Radix, Counting).

Everything in this guide cross-checks against these. The interactive visualisers are especially worth a few minutes — watching the algorithms run locks intuition in faster than any prose can.

// ── Books ────────────────────────────────────────────
//
//  • CLRS — Cormen, Leiserson, Rivest, Stein
//    "Introduction to Algorithms", 4th ed. (MIT Press, 2022)
//    The standard reference for the field. Chapters 2, 6–8.
//
//  • Sedgewick & Wayne — "Algorithms", 4th ed.
//    Friendlier than CLRS. Java code. Pairs with the Coursera course.
//
//  • Knuth — "TAOCP Vol 3: Sorting and Searching"
//    The deep end. Reach for it when you want to read the bedrock
//    of the field. Not for first-time learning.
//
//  • Skiena — "The Algorithm Design Manual", 3rd ed.
//    Practical, problem-solving focus. Great companion to CLRS.

// ── Free university courses (best of the best) ───────
//
//  • MIT 6.006 — Introduction to Algorithms (Erik Demaine et al.)
//    https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
//    Lectures 3–7 cover sorting comprehensively. Free, on YouTube too.
//
//  • Princeton Algorithms (Sedgewick) on Coursera
//    Both Algorithms I & II free to audit. Pairs with Sedgewick's book.
//
//  • Stanford CS161 (Tim Roughgarden)
//    Lecture notes free online. Excellent on Quick Sort analysis.

// ── Interactive visualisers ──────────────────────────
//
//  • https://visualgo.net/en/sorting
//    Step through every sort. Side-by-side mode. Best in class.
//
//  • https://sorting.at/
//    Race multiple sorts on the same input. Eye-opening.
//
//  • https://www.toptal.com/developers/sorting-algorithms
//    Animated, classic distributions (random, sorted, reverse, ...).

// ── Quick-reference sites ────────────────────────────
//
//  • https://en.wikipedia.org/wiki/Sorting_algorithm    overview
//  • https://www.bigocheatsheet.com/                    Big O at a glance
//  • https://www.geeksforgeeks.org/sorting-algorithms/  many implementations
//  • https://learn.microsoft.com/dotnet/api/system.array.sort  .NET specifics

// ── Papers / talks worth your time ───────────────────
//
//  • Robert Sedgewick — "Quicksort is optimal" (1977)
//    The original average-case analysis. Still beautiful.
//
//  • David Musser — "Introspective Sorting and Selection Algorithms" (1997)
//    The IntroSort paper. 8 pages. Read it to understand
//    why .NET's Array.Sort is the way it is.
//
//  • Tim Peters — "List sort algorithm description" (CPython source)
//    The original TimSort note. Lives in cpython/Objects/listsort.txt.

// ── Want to keep going? ──────────────────────────────
//
//  Searching → binary search and its variants
//  Data structures → trees, heaps (you've already met heaps!), graphs
//  Algorithms → BFS, DFS, dynamic programming
//
//  You already know enough about Big O to start any of them today.
//  Head to the "Algorithms & Data Structures" full guide on this site.