Sorting Under Constraint

Sorting under firmware constraints

Pick the sort from the constraint that binds, not from the average complexity table. Small and nearly sorted means insertion sort. A hard worst-case bound with no recursion means heapsort. A small key space means counting sort. Only k items matter means a bounded heap, not a sort at all. Library qsort is the one to justify rather than the one to default to, because its recursion depth is not something you control.

The complexity table taught in a general course ranks sorts by average time, which is the least useful axis in firmware. A microcontroller cares about the worst case, the extra memory, and whether the routine recurses - and on those three axes the ranking is completely different. Heapsort is unfashionable and is often the correct answer, because it is the only common sort that is simultaneously O(n log n) worst case, O(1) space, and entirely iterative.

Insertion sort is not a beginner's mistake. It is O(n) on already-sorted input, has almost no constant factor, needs no memory, and is stable. For the n under about thirty-two that firmware actually sorts - a window of samples, a handful of events - it beats every asymptotically better algorithm, which is why every serious library falls back to it below a threshold.

Sorting is often the wrong tool entirely. If you need the largest k, a bounded heap costs O(n log k) and O(k) memory instead of sorting everything. If the keys are bytes, counting sort is O(n) with a fixed table. If there are three categories, a single three-way partition pass is enough. Reaching for a general sort when the problem has structure is how an O(n) job becomes an O(n log n) one.

Patterns and when they apply

insertion sort

n below ~32, nearly sorted data, stability required. Cost: O(n²) worst, O(n) on sorted input, O(1) space. Avoid when: Large n with random order.

heapsort

A hard worst-case bound with no recursion and no extra RAM. Cost: O(n log n) always, O(1) space. Avoid when: When stability matters - heapsort is not stable.

counting sort

Small known key space, such as byte-valued samples. Cost: O(n + k) time, O(k) fixed table. Avoid when: Wide or unbounded key ranges.

bounded heap for top-k

Only the k best matter out of n. Cost: O(n log k) time, O(k) space. Avoid when: When you actually need the whole order.

Choosing a sort for a 24-sample median filter

1. n is 24 and fixed, so asymptotic behaviour is irrelevant - the constant factor decides.
2. The window moves by one sample, so the input is almost sorted every time.
3. The filter runs in a control loop, so the worst case must be bounded and the stack must not grow.
4. Insertion sort: O(n) on nearly sorted data, no recursion, no memory, and about twenty lines.

Insertion sort wins on every axis that binds here, and qsort would have been slower and less predictable.

Checklist

• What is n, really?
• Is the input nearly sorted already?
• Does the worst case have to be bounded?
• How much stack does it use?
• Does stability matter?
• Do you need the whole order, or just the top few?

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

• 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.
• 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 & ArenasIntrusive linked lists, fixed-block pools, arena allocators and why malloc is banned in most firmware. Ten problems on owning memory with a bound you can prove before the board ships.
• 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.
• Heaps & SchedulingBinary heaps as timer wheels and task schedulers, and wrap-safe time comparison - the bug that only shows up 49 days after the board is deployed. Eight problems with complete solutions.
• 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.
• 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.
• 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.