Sorting Under Constraint
How does insertion sort put one new reading in its place?
Insertion sort
Pick up the next record, keep it safe in a temporary variable, and shift larger predecessors right until its position opens. You are inserting into an already ordered prefix—not searching for the global minimum. The amount of movement depends on how disordered the input is.
For [7,3,5], hold 3, shift 7, place 3: [3,7,5]. Then hold 5, shift 7, stop at 3, and place 5: [3,5,7]. With [3A,3B], using > rather than >= means B never jumps before A.
for i = 1 .. n-1:
held = a[i]
j = i
while j > 0 and a[j-1].key > held.key:
a[j] = a[j-1]
j = j-1
a[j] = heldThe algorithm above is language-neutral pseudocode.
A good baseline for small buffers and nearly ordered windows. Reverse order requires n(n−1)/2 shifts. A quadratic algorithm can still be the sensible choice for eight records; do not confuse asymptotic growth with measured small-input cost.
Predict the number of successful shifts on [4,3,2,1]. What changes on [1,2,3,4]?
Reverse order shifts 1+2+3=6 records. Sorted order shifts none, but still compares each new record with its predecessor. Both use one held record.
Selection sort
Scan the entire remaining suffix, remember where its minimum lives, then exchange that record with the first unsorted position. Unlike insertion, selection does not benefit much from input already being ordered: it still has to establish that no smaller candidate remains.
In [3A,3B,1C], the first pass swaps 1C with 3A, yielding [1C,3B,3A]. The keys are on their way to being sorted but the two 3s have reversed their original order. A nonadjacent swap can break stability.
for i = 0 .. n-2:
minimum = i
for j = i+1 .. n-1:
if a[j].key < a[minimum].key:
minimum = j
swap a[i], a[minimum]The algorithm above is language-neutral pseudocode.
It performs n(n−1)/2 key comparisons and at most n−1 nontrivial swaps. Useful for understanding the distinction between comparison cost and movement cost; reducing RAM writes is not by itself a safe flash-update algorithm.
Does finding a small value early let selection sort stop scanning the suffix?
No, unless you have extra knowledge such as a proven minimum possible key. A later value might be smaller. Ordinary selection scans every remaining candidate.
Bubble sort
Compare neighbouring records and swap an out-of-order pair. A left-to-right pass pushes the largest unsettled key to the right boundary. The next pass can ignore that final suffix. The useful lesson is how local repairs establish a global invariant.
[3,2,1] becomes [2,3,1] after the first comparison, then [2,1,3]. The largest key is final, but 2 and 1 still need another pass. Seeing one pair in order is not evidence that the whole range is ordered.
for end = n-1 down to 1:
changed = false
for j = 0 .. end-1:
if a[j].key > a[j+1].key:
swap a[j], a[j+1]
changed = true
if not changed: breakThe algorithm above is language-neutral pseudocode.
Simple to trace but often more movement than insertion. With a no-swap flag, already sorted input finishes in one pass. Without that optimisation the best case is still quadratic. The lab includes the flag.
Why does one entire pass with no swaps prove that you can stop?
Every adjacent pair is ordered. By transitivity the entire active range is ordered, and the suffix was already final. One single comparison without a swap is insufficient.
Shell sort
Insertion sort moves an element only one place at a time. Shell sort first orders chains of elements several positions apart. Long moves reduce coarse disorder; the final gap-one pass is ordinary insertion sort on the partially organised result.
For eight elements and gap 4, compare the chains (0,4), (1,5), (2,6), (3,7). Gap 2 then connects those groups differently; gap 1 finishes the order. Watch the highlighted indices jump rather than slide next to each other.
gap = floor(n/2)
while gap >= 1:
for i = gap .. n-1:
held = a[i]; j = i
while j >= gap and a[j-gap].key > held.key:
a[j] = a[j-gap]; j -= gap
a[j] = held
gap = floor(gap/2)The algorithm above is language-neutral pseudocode.
In-place and iterative, but bounds depend on the gap sequence. This lab halves the gap each time; its worst case is O(n²). Do not quote one universal Shell-sort average or promise stable ordering across long-distance moves.
If the gap-2 chains are sorted, why do you still need gap 1?
Indices of opposite parity belong to different chains. [2,1,4,3] has sorted even and odd chains, yet adjacent pairs are inverted. Gap 1 links the whole array.
Merge sort
Two sorted runs can be combined by comparing only their front records. Whichever is smaller is the next record in the combined run. Begin with runs of length one; merge into length two, then four, then eight. This bottom-up version needs no recursive calls.
Merge [2A,5B] and [2C,4D]. Choose 2A on the tie, then 2C, then 4D, and finally 5B. Choosing left first on equality retains record order across the original halves.
width = 1
while width < n:
for each pair of runs of length width:
while either run has records:
take smaller front into temporary output
on equal keys, take left first
copy output back into the two-run range
width *= 2The algorithm above is language-neutral pseudocode.
Predictable O(n log n) work with stable record ordering, but the ordinary array implementation needs O(n) auxiliary records. Here both temporary-output and copy-back writes are counted. For linked lists, merging can relink nodes instead of allocating an array.
Why does merging cost linear work while the whole algorithm costs n log n?
Each merge moves through its two runs once. Across one width level, the runs cover at most n records. Roughly log₂n width levels are needed, so total work is proportional to n log n.
Quicksort
Choose a pivot and divide the range into keys below it and keys at least as large. Put the pivot between those groups, then sort each group. Partitioning establishes a boundary, not sorted subarrays. The lab deliberately uses a last-element pivot so the bad cases remain visible.
For [4,1,3,2], pivot=2. Move 1 into the smaller region, then put 2 after it: [1,2,3,4]. That example happens to finish both sides too, but [5,3,4,2,1] does not. Each nontrivial side still needs its own partition.
push [0,n-1] onto work stack
while stack is not empty:
pop [lo,hi]; pivot = a[hi]; p = lo
for j = lo .. hi-1:
if a[j].key < pivot.key:
swap a[j], a[p]; p++
swap a[p], a[hi]
push nontrivial left and right partitionsThe algorithm above is language-neutral pseudocode.
Balanced partitions give O(n log n); last-pivot sorted or equal-key input can give O(n²). The lab uses an explicit pending-range stack, conservatively O(n) auxiliary capacity. A smaller-side-first implementation can bound stack depth without fixing quadratic comparison work. Introsort adds a worst-case fallback.
Why can bounding recursion depth still leave unacceptable worst-case latency?
Stack depth measures simultaneous saved work. Repeatedly partitioning n−1 records still performs quadratic comparisons even if the larger side is processed iteratively. Memory and time need separate arguments.
Heapsort
Interpret the array as a complete binary tree, with children 2i+1 and 2i+2. Build a max-heap: every parent is at least its children. Swap the root with the last heap element, shrink the heap, and sift the replacement downward. The sorted suffix grows right to left.
A max-heap [9,6,7,2] is not sorted. Swap the root with 2: [2,6,7,9]. The 9 is final. Compare 2 with children 6 and 7, choose larger child 7, and swap to get [7,6,2,9].
for root = floor(n/2)-1 down to 0:
sift_down(root, n)
for end = n-1 down to 1:
swap a[0], a[end]
sift_down(0, end)
# sift_down: compare with the larger child;
# swap and continue until parent is >= childThe algorithm above is language-neutral pseudocode.
O(n log n) worst-case work with O(1) auxiliary algorithm storage and no recursion. It is not stable and can have less favourable locality than sequential merges. Heap construction is O(n), not O(n log n): most starting nodes are near leaves and sift only a short distance.
Why is swapping with the smaller child during max-heap repair wrong?
The larger child would still exceed the new parent. Choose the larger child so the parent position satisfies both child comparisons after the exchange; continue repairing below.
Counting sort
Count how many records have each key. Prefix totals then identify the output region assigned to each key. Place records into their assigned positions while maintaining their original order. This replaces key comparisons with indexed counting; it relies on keys being integers in a manageable range.
For [2A,0B,2C,1D], counts are [1,1,2]. The starting offsets for keys 0,1,2 are [0,1,2]. Traverse input left to right: 2A goes to slot 2, 0B to 0, 2C to 3 and 1D to 1. Output is [0B,1D,2A,2C].
count[0..k) = 0
for record in input: count[record.key]++
start[0] = 0
for key = 1 .. k-1:
start[key] = start[key-1] + count[key-1]
for record in input, left to right:
output[start[record.key]++] = record
copy output to inputThe algorithm above is language-neutral pseudocode.
O(n+k) time and O(n+k) storage for this stable record version, where k is the key range. Sorting a few arbitrary 32-bit keys with a direct count per possible key is usually impractical. A value-only histogram rewrite can use less space but discards record identity.
Why does O(n+k) not violate the comparison-sorting lower bound?
It is not restricted to comparing pairs of arbitrary keys. It exploits integer key values as array indices and pays for the universe size k. The comparison lower bound has different assumptions.
LSD radix sort
Sort by the least significant digit first, preserving order within each digit. Then sort stably by the next digit. On a tie in the more significant digit, the previous pass has already ordered the less significant digits. Repeat until all significant digits have been processed.
[21,13,12] enters units bins 1:[21], 2:[12], 3:[13], producing [21,12,13]. The tens pass puts 12 and 13 together in that order, then 21: [12,13,21]. An unstable tens pass could wrongly turn 12,13 into 13,12.
for place = 1, 10, 100, ... through largest key:
empty bins 0..9
for record in current order:
digit = floor(record.key / place) % 10
append record to bin[digit]
concatenate bins in digit order
# Appending preserves order inside each bin.The algorithm above is language-neutral pseudocode.
O(d(n+b)) time and O(n+b) auxiliary storage with d digits and base b. The lab uses decimal bins for visibility; fixed-width firmware often uses byte-sized digits. Signed integers require an order-preserving treatment of the sign, not blindly reusing unsigned digit order.
Why would sorting the tens digits first and then units fail with these same passes?
The last pass would make units the primary key. For [12,21], a tens pass keeps [12,21], then a units pass produces [21,12]. MSD radix needs a different recursive grouping strategy.
Bucket sort
Map keys to ordered ranges, sort inside each bucket, then concatenate. Counting sort uses exact key positions; buckets can contain several distinct keys. Expected near-linear performance needs a suitable distribution and bucket count. One crowded bucket can fall back to quadratic work if its internal sort is insertion sort.
Introsort
Begin with quicksort, monitor partition depth, and fall back to heapsort when depth grows too large; use insertion sort for tiny partitions. This combines typical partitioning performance with an O(n log n) worst-case bound. A production hybrid is more than simply changing the pivot once.
Timsort / adaptive merging
Discover already sorted runs, extend short runs, and merge with carefully managed run sizes. Stable adaptive merging exploits existing order; it still needs auxiliary storage and a correct merge policy. Useful to understand why a library sort need not behave like textbook merge sort.
External merge sorting
When records exceed RAM, sort chunks that fit, write runs, then merge them with bounded input buffers. The dominant cost becomes transfers rather than only key comparisons. A heap can choose the next head among several streams. Account for media endurance and crash recovery on flash.
Sorting networks and top-k
A fixed compare-exchange network can suit a tiny fixed-size median filter or parallel hardware; it is not a general variable-length replacement. If only k extreme records are needed, a bounded heap or selection algorithm may avoid sorting everything. Begin by asking what output is actually required.
Easy - Insertion Sort a Small Sample Window
Sorting the small window inside a median filter, or ordering a handful of events before dispatch. The n that firmware actually sorts is almost always under thirty-two.
Sort a small array of uint16_t samples ascending, in place, with no recursion and no extra buffer. It must be stable and must do near-zero work on data that is already sorted.
Insertion sort, stable and linear on sorted input
Sorts v[0..n) ascending in place. Stable: equal values keep their original relative order. n of 0 or 1, or a NULL pointer, is a no-op.
#include <stddef.h>
#include <stdint.h>
void sort_window(uint16_t *v, size_t n) {
if (v == NULL || n < 2u) {
return;
}
for (size_t i = 1u; i < n; i++) {
const uint16_t key = v[i];
size_t j = i;
/* Strict > keeps the sort stable: an equal value stops the shift,
so it never moves past an equal element that came before it. */
while (j > 0u && v[j - 1u] > key) {
v[j] = v[j - 1u];
j--;
}
v[j] = key;
}
}- The invariant is that v[0..i) is sorted before each outer iteration. The body extends it by one by lifting v[i] out and shifting every larger element right until the hole is in the right place.
- Using a strict greater-than in the shift condition is what makes it stable. With >= an equal element would be shifted past, reversing the order of equal keys - which is exactly what breaks a priority sort that must preserve arrival order.
- On already-sorted input the while condition fails immediately every time, so the whole sort is n-1 comparisons and no writes. That is the property that makes it the right choice for a sliding window, where each new sort differs from the last by one element.
- j is size_t and the guard is j > 0 before reading v[j-1], so the index never underflows. Writing the loop as j >= 0 with a signed j is the classic form and is a bug waiting for someone to change the type.
Cases the tests must cover
- [5,1,4,2,8] → [1,2,4,5,8]
- Already sorted [1,2,3,4] → unchanged, n-1 comparisons, zero shifts
- Reverse sorted [4,3,2,1] → [1,2,3,4], the worst case
- Equal keys preserve input order (stability)
- n = 0, n = 1, and NULL are all no-ops
How it gets written wrong
- Using >= in the shift test, which silently destroys stability.
- A signed loop index compared >= 0, which underflows if the type is later made unsigned.
- Shifting with a swap in the inner loop, which does three assignments where one suffices.
Medium - Heapsort With a Provable Worst Case
Anywhere the deadline is fixed and the stack is small: ordering a batch inside a control loop, or sorting on a task with a 512-byte allocation.
Sort an array in place using heapsort: build a max-heap, then repeatedly swap the root to the end and sift down. No recursion anywhere, and the same cost whatever the input.
Heapsort: O(n log n) worst case, no recursion, no extra memory
Sorts v[0..n) ascending in place. Cost is identical for every input. Uses no recursion and no memory beyond a few locals. Not stable.
#include <stddef.h>
#include <stdint.h>
/* Restore the max-heap property at `root` within v[0..n). Iterative:
the loop walks down the tree instead of calling itself. */
static void sift_down(uint32_t *v, size_t n, size_t root) {
for (;;) {
size_t largest = root;
const size_t l = 2u * root + 1u;
const size_t r = l + 1u;
if (l < n && v[l] > v[largest]) { largest = l; }
if (r < n && v[r] > v[largest]) { largest = r; }
if (largest == root) {
return; /* heap property holds below here */
}
const uint32_t t = v[root];
v[root] = v[largest];
v[largest] = t;
root = largest; /* continue down, no recursion */
}
}
void heap_sort(uint32_t *v, size_t n) {
if (v == NULL || n < 2u) {
return;
}
/* Build: every node from the last parent down to the root. */
for (size_t i = n / 2u; i-- > 0u; ) {
sift_down(v, n, i);
}
/* Drain: the root is the maximum, so swap it to the end and shrink. */
for (size_t end = n - 1u; end > 0u; end--) {
const uint32_t t = v[0];
v[0] = v[end];
v[end] = t;
sift_down(v, end, 0u);
}
}- The array is treated as a complete binary tree: the children of index i are 2i+1 and 2i+2. No pointers and no node allocation are involved - the tree is implied by the arithmetic.
- The build phase starts at the last parent, n/2 - 1, and works backwards. Starting at the leaves would be wasted work: a leaf is already a valid heap of one element.
- The drain phase gives the algorithm its guarantee. Each iteration moves the current maximum to its final position and sifts down over a region one element smaller, so the total is n sift-downs of depth at most log2(n) - and that holds for every input, with no pivot to choose badly.
- sift_down is a loop rather than a recursive call, so the stack usage is a fixed handful of locals. This is the property that makes heapsort usable in a task with a 512-byte stack where a recursive sort cannot be trusted.
- The build loop is written `for (size_t i = n / 2u; i-- > 0u; )` so that an unsigned index can walk down to zero and stop, without ever evaluating i-1 at i == 0.
Cases the tests must cover
- Random input sorts correctly
- Already sorted and reverse sorted both cost the same as random
- All-equal input sorts without infinite looping
- n = 0, 1, 2 handled; NULL is a no-op
- Stack usage is constant regardless of n
How it gets written wrong
- Writing sift_down recursively, which reintroduces the unbounded stack the algorithm was chosen to avoid.
- Starting the build at n/2 rather than n/2 - 1, which either wastes a pass or skips a parent depending on how the loop is written.
- Sifting over the full array during the drain instead of the shrinking region, which corrupts the already-placed tail.
- Assuming stability - heapsort is not stable, and using it to order equal-priority events loses arrival order.
Easy - Counting Sort of Byte-Valued Samples
Ordering byte-valued data: sorting pixel intensities for a median, ranking 8-bit sensor readings, or building an ordered histogram.
Sort an array of uint8_t samples using a 256-entry count table, then write the values back in order. One pass to count, one pass to emit.
Counting sort over a 256-entry key space
Sorts v[0..n) ascending in place using a fixed 256-entry table. Time is linear in n plus the key space, independent of the input's order.
#include <stddef.h>
#include <stdint.h>
void counting_sort(uint8_t *v, size_t n) {
if (v == NULL || n < 2u) {
return;
}
/* size_t counts, not uint8_t: n can exceed 255 and the count must not
wrap. This table is 1 KB on a 32-bit part - budget it deliberately. */
size_t count[256] = {0};
for (size_t i = 0u; i < n; i++) {
count[v[i]]++;
}
size_t w = 0u;
for (size_t value = 0u; value < 256u; value++) {
for (size_t k = 0u; k < count[value]; k++) {
v[w] = (uint8_t)value;
w++;
}
}
}- The key space is the whole of uint8_t, so the count table can be a fixed 256 entries with no search and no hashing. The value itself is the index - the array IS the map.
- Two passes and no comparisons at all. The cost is n increments plus a walk of 256 buckets, which beats any comparison sort as soon as n is more than about a thousand and is completely independent of how the input is ordered.
- The counts are size_t rather than a narrow type, because n can exceed what a uint8_t counter holds. A wrapped count silently drops 256 samples per bucket, which produces a plausible but wrong result.
- The output loop writes values back in ascending key order, so w ends exactly at n. Because equal keys are indistinguishable here, stability is not meaningful for plain values - it becomes meaningful only when sorting records by a byte key, which needs the prefix-sum variant.
Cases the tests must cover
- Random bytes sort correctly
- All-equal input produces one full bucket
- n larger than 255 does not wrap any counter
- Empty and single-element inputs are no-ops
- Cost is identical for sorted, reversed and random input
How it gets written wrong
- Declaring the count table as uint8_t, which wraps once a value appears more than 255 times.
- Putting a 1 KB table on the stack of a small task - it belongs in static storage or in a caller-provided buffer.
- Assuming this generalises to wide keys: at 16 bits the table is 256 KB and the technique stops being viable.
Medium - Top-K Without Sorting the Rest
Keeping the strongest few out of a stream: the loudest channels, the nearest beacons, the k worst readings for a diagnostic report.
Return the k largest values from n samples in descending order without sorting the whole array, keeping only k elements of working state.
Top-k with a bounded min-heap
Writes the k largest values of v[0..n) into out[0..k) in descending order and returns the count written, which is min(k, n). Uses O(k) working state and never sorts the input.
#include <stddef.h>
#include <stdint.h>
static void sift_down_min(uint16_t *h, size_t n, size_t root) {
for (;;) {
size_t small = root;
const size_t l = 2u * root + 1u;
const size_t r = l + 1u;
if (l < n && h[l] < h[small]) { small = l; }
if (r < n && h[r] < h[small]) { small = r; }
if (small == root) { return; }
const uint16_t t = h[root];
h[root] = h[small];
h[small] = t;
root = small;
}
}
size_t top_k(const uint16_t *v, size_t n, uint16_t *out, size_t k) {
if (v == NULL || out == NULL || k == 0u) {
return 0u;
}
size_t held = 0u;
for (size_t i = 0u; i < n; i++) {
if (held < k) {
/* Fill phase: insert, then restore the min-heap upward. */
out[held] = v[i];
size_t c = held;
held++;
while (c > 0u) {
const size_t parent = (c - 1u) / 2u;
if (out[parent] <= out[c]) { break; }
const uint16_t t = out[parent];
out[parent] = out[c];
out[c] = t;
c = parent;
}
} else if (v[i] > out[0]) {
/* out[0] is the smallest of the k best so far: replace it. */
out[0] = v[i];
sift_down_min(out, k, 0u);
}
}
/* Heap-sort the result in place to hand it back descending. */
for (size_t end = held; end > 1u; end--) {
const uint16_t t = out[0];
out[0] = out[end - 1u];
out[end - 1u] = t;
sift_down_min(out, end - 1u, 0u);
}
return held;
}- The heap is a MIN-heap even though we want the largest values, which is the part that trips people up. The root is the weakest member of the current best k, so it is exactly the element to evict when something better arrives.
- Once the heap holds k elements, each further sample costs one comparison against the root and, only if it wins, a sift of depth log2(k). Most samples in a real stream lose that comparison and cost a single compare.
- Working state is the k-element output buffer itself - the caller's memory - so the function allocates nothing. This is what lets it run over a stream of unbounded length in fixed RAM.
- The final loop drains the min-heap into the same array, which leaves it in descending order. Draining a min-heap writes ascending values from the back, so the array ends up largest-first without a second buffer.
Cases the tests must cover
- k = 1 returns the single maximum
- k >= n returns all n values, sorted descending
- k = 0 returns 0 and writes nothing
- Duplicate values are all eligible
- A stream far larger than k uses no additional memory
How it gets written wrong
- Using a max-heap, which makes finding the element to evict O(k) instead of O(1).
- Sorting the whole input and taking the first k, which costs O(n log n) and needs the whole array in RAM.
- Forgetting that the result is a heap, not a sorted array, and handing it back unordered.
Medium - Stable Ordering by Priority
Ordering an event queue by priority where equal-priority events must still be served in arrival order - the fairness property every dispatcher is assumed to have.
Order events by priority so that events of equal priority keep their arrival order. Prove stability rather than relying on the sort happening to preserve it.
Stable priority ordering that preserves arrival
Orders e[0..n) by ascending priority. Events with equal priority keep their input order. In place, no allocation.
#include <stddef.h>
#include <stdint.h>
typedef struct {
uint8_t priority; /* 0 is most urgent */
uint16_t seq; /* arrival order, assigned by the producer */
uint16_t payload;
} event_t;
void sort_events(event_t *e, size_t n) {
if (e == NULL || n < 2u) {
return;
}
for (size_t i = 1u; i < n; i++) {
const event_t key = e[i];
size_t j = i;
/* Strict > on priority alone. Equal priorities never shift past
each other, so arrival order survives without comparing seq. */
while (j > 0u && e[j - 1u].priority > key.priority) {
e[j] = e[j - 1u];
j--;
}
e[j] = key;
}
}- Stability here is a property of the algorithm, not of the comparison. Insertion sort with a strict greater-than never moves an element past an equal one, so equal priorities come out in the order they went in.
- The seq field is carried so that stability can be asserted in a test, and so a caller can restore arrival order if it needs to. It is deliberately not part of the comparison - comparing it would impose order rather than preserve it, which hides a bug in the sort.
- The alternative is to make the key a pair of (priority, seq) and use any sort at all. That works, costs an extra field comparison on every step, and requires the sequence number to be monotonic - which it is not, once it wraps.
- Whole structs are assigned rather than swapped field by field, so adding a field to event_t cannot leave the sort copying a subset of it.
Cases the tests must cover
- Equal priorities emerge in ascending seq order
- Strictly decreasing priorities reverse fully
- Already ordered input performs no shifts
- Single element and empty inputs are no-ops
- Adding a field to event_t does not change the result
How it gets written wrong
- Using >= in the comparison, which reverses equal-priority events and turns a fair queue into an unfair one.
- Using heapsort or qsort here - neither is stable, so equal-priority events come out in an arbitrary order that varies with input.
- Comparing seq as a tiebreak without handling its wrap, which reorders events once the counter rolls over.
Hard - Bound Quicksort's Stack Depth
Using the average speed of quicksort on a part where the stack is a budgeted resource and overflow is silent corruption rather than a caught exception.
Implement quicksort so that stack depth is bounded by log2(n) regardless of pivot quality: recurse into the smaller partition and loop on the larger one.
Quicksort with a stack depth bounded by log2(n)
Sorts v[0..n) ascending. Recursion depth never exceeds log2(n) frames regardless of pivot quality, because only the smaller partition is recursed into.
#include <stddef.h>
#include <stdint.h>
static size_t partition(uint32_t *v, size_t lo, size_t hi) {
/* Median-of-three pivot, moved to hi-1, to avoid the sorted-input
worst case that a first- or last-element pivot produces. */
const size_t mid = lo + (hi - lo) / 2u;
if (v[mid] < v[lo]) { const uint32_t t = v[mid]; v[mid] = v[lo]; v[lo] = t; }
if (v[hi] < v[lo]) { const uint32_t t = v[hi]; v[hi] = v[lo]; v[lo] = t; }
if (v[hi] < v[mid]) { const uint32_t t = v[hi]; v[hi] = v[mid]; v[mid] = t; }
const uint32_t pivot = v[mid];
size_t i = lo;
size_t j = hi;
for (;;) {
while (v[i] < pivot) { i++; }
while (v[j] > pivot) { j--; }
if (i >= j) { return j; }
const uint32_t t = v[i];
v[i] = v[j];
v[j] = t;
i++;
j--;
}
}
void bounded_qsort(uint32_t *v, size_t n) {
if (v == NULL || n < 2u) {
return;
}
size_t lo = 0u;
size_t hi = n - 1u;
while (lo < hi) {
const size_t p = partition(v, lo, hi);
/* Recurse into the SMALLER side; loop on the larger one.
The recursed side is at most half the range, so depth is
bounded by log2(n) even when every pivot is terrible. */
if ((p - lo) < (hi - p)) {
bounded_qsort(&v[lo], p - lo + 1u);
lo = p + 1u;
} else {
bounded_qsort(&v[p + 1u], hi - p);
hi = p;
}
}
}- The bound comes from one decision: recurse into the smaller partition and iterate on the larger. The recursed range is at most half of what remains, so the depth cannot exceed log2(n) - about 12 frames for 4096 elements - no matter how badly the pivots split.
- The naive form recurses into both halves, and on already-sorted input with a first-element pivot that gives n nested frames. On a 512-byte task stack, a thousand-element sort is a guaranteed overflow. This is the failure the whole exercise exists to prevent.
- Median-of-three does not change the worst-case bound - only the smaller-side rule does that - but it removes the common cases that produce it, so the average behaviour stays close to n log n on real data.
- The tail is converted into a loop by reassigning lo or hi, which is what a compiler's tail-call optimisation would do if it were guaranteed. It is not guaranteed, so it is written out explicitly.
- This is still worse than heapsort for a hard real-time path: the time bound remains O(n²) in the worst case even though the stack bound is now safe. Use it where average speed matters and the stack must not blow; use heapsort where the deadline is the constraint.
Cases the tests must cover
- Already sorted input does not exceed log2(n) depth
- Reverse sorted input does not exceed log2(n) depth
- All-equal input terminates rather than looping
- Random input sorts correctly
- Measured stack depth grows logarithmically, not linearly
How it gets written wrong
- Recursing into both partitions, which is the textbook form and has an unbounded stack.
- Choosing the first or last element as pivot, which makes sorted input the worst case - the most common input in firmware.
- Expecting a bounded stack to imply a bounded time: this fixes the depth, not the O(n²) worst-case runtime.
More in Embedded DSA
- Arrays & WindowsTwo pointers, sliding windows, in-place compaction and streaming filters over sample buffers. Twelve problems with complete C11 solutions, complexity targets and edge-case tests.
- Search & LookupBinary search that actually terminates, lookup tables, perfect hashing and command dispatch. Eleven problems on getting a bounded answer out of a table without a heap allocation in sight.
- Lists, Pools & ArenasFollow packet storage through allocation, use and release. Compare fixed-block pools, linked lists and arenas, including exhaustion, lifetime and allocation trade-offs.
- Trees, Graphs & StateTries for command tables, union-find for connectivity, and state machines that cannot reach an undefined state. Nine problems on structures that encode relationships rather than sequences.
- Parsing & ProtocolsFraming, COBS, incremental parsers and adversarial input. Nine problems on decoding a byte stream from a hostile world without a buffer overflow or an unbounded loop.
- Linked ListsEvery list variant, written for embedded C rather than for a whiteboard: singly and doubly linked, circular lists and sentinels that delete the boundary cases, the intrusive form kernels and firmware actually use, static pools and free lists for systems without malloc, reversal and cycle detection, and an honest account of when an array is the better answer.
- The WorkbenchA complete embedded-first DSA course with theory, 80 challenges, complete C11 implementations, visual traces, mastery tracking, interview drills, and a constraint-driven firmware design arena.
- Heaps & SchedulingInsert and remove deadlines in a binary min-heap, then study scheduling and wrapping tick counters. Heaps and timer wheels are different timer-management structures.
- Stacks, Queues & RingsThe ring buffer and the SPSC queue: the two structures every firmware project actually ships. Ownership between an ISR and a main loop, overflow policy, and why the full/empty test is where the bugs are.
- Bits & BytesRegister fields, bit reversal, parity, endianness and portable packet decoding, without invoking undefined behaviour. Seven problems with complete C11 solutions and a step-by-step trace for each.
- Integer & Fixed-Point MathComputing the right number with no floating-point unit. Q formats, multiply-before-divide, rounding instead of truncating, division by a constant as a multiply and shift, running averages that do not stall, and LFSR jitter for backoff.
- Firmware CapstonesSix full-system problems: DMA ownership, wear-levelled persistence, crash-safe logging and proving a design meets its RAM and WCET budget. This is where every earlier stage gets used at once.