Embedded DSA Interview Questions: Heap and Sorting (Q189–Q218)

Part 6 of the seven-part Embedded Firmware DSA Interview Guide — 30 questions answered at full depth for embedded, firmware and senior technical roles.

Sorting algorithms interview questions for embedded roles are rarely about reproducing quick sort from memory. They are about which sort you would actually ship when RAM is fixed, writes are expensive, and a worst case has to go into the design document. Thirty questions on heaps and sorting, answered that way.

---

Heap and sorting algorithms interview questions for embedded roles

• Q189. What is a max heap?
• Q190. What is a min heap?
• Q191. What does heapify do and what does it cost?
• Q192. How do you insert into a heap?
• Q193. How do you extract the root from a heap?
• Q194. How does heap sort work and when do you choose it?
• Q195. How does a heap implement a priority queue?
• Q196. What are the time complexities of heap operations?
• Q197. How do you build a timer scheduler on a min heap?
• Q198. Where are heaps used in embedded systems?
• Q199. How does bubble sort work and is it ever the right choice?
• Q200. How does selection sort work and when does it win?
• Q201. Why is insertion sort fast on nearly sorted data?
• Q202. How does merge sort work and what does it cost in memory?
• Q203. How does quick sort work and what is its worst case?
• Q204. When do you choose heap sort over quick sort?
• Q205. How does counting sort beat O(n log n)?
• Q206. How does radix sort work?
• Q207. How does bucket sort work and when does it degrade?
• Q208. How does shell sort improve on insertion sort?
• Q209. Which sorts are stable?
• Q210. Which sorts are in place?
• Q211. What is the worst case for each sorting algorithm?
• Q212. What is the best case for each sorting algorithm?
• Q213. What is the average case for each sorting algorithm?
• Q214. Which sort for embedded?
• Q215. Why does merge sort need extra memory?
• Q216. How do you choose a quick sort pivot?
• Q217. What is hybrid sorting and why does introsort exist?
• Q218. What algorithms do std::sort and std::stable_sort use?

---

Questions 189 to 218, explained fully.

---

Section 11: Heap

---

Q189. What is a max heap?

Say this out loud A complete binary tree where every parent is greater than or equal to both of its children. The largest element is therefore always at the root and readable in O(1). Because the tree is complete, it is stored in a flat array with no pointers at all.

The full explanation

Two rules, and both must hold:

1. Shape rule. The tree is complete: every level full except possibly the last, which fills from the left. This is what permits the array representation from Q155.
2. Order rule. parent >= child for every node. Note this is a partial order, not a total one. A heap is not sorted. Siblings have no defined relationship to each other.

            50
          /    \
        30      40
       /  \    /
     10   20  35

array: [50, 30, 40, 10, 20, 35]
index:   0   1   2   3   4   5

Check the index arithmetic: node 30 is at index 1, so its children are at 3 and 4, which are 10 and 20. Correct. Node 40 is at index 2, children at 5 and 6, and 6 is past the end so it has only one child, 35. Correct.

#define HEAP_MAX 64

typedef struct {
    int data[HEAP_MAX];
    int size;
} heap_t;

static inline int parent(int i) { return (i - 1) / 2; }
static inline int lchild(int i) { return 2 * i + 1; }
static inline int rchild(int i) { return 2 * i + 2; }

The partial order point matters. In the heap above, 35 is greater than 30, yet 30 is closer to the root. That is perfectly legal, because they are in different subtrees. Candidates who expect a heap to be sorted get confused when they print the array and it looks wrong. Say explicitly that a heap only guarantees the root, nothing else.

Why the array representation is the whole appeal for firmware. No left and right pointers means 4 bytes per element instead of 12, no allocation, contiguous memory, and the entire structure can be a fixed array in .bss whose size is visible in the linker map.

---

Q190. What is a min heap?

Identical, with the comparison inverted: every parent is less than or equal to its children, so the smallest element is at the root.

            10
          /    \
        20      15
       /  \
     30   25

array: [10, 20, 15, 30, 25]

The only implementation difference is one comparison operator. Good code parameterises it:

typedef bool (*cmp_fn)(int a, int b);        /* returns true if a should be above b */

static bool max_cmp(int a, int b) { return a > b; }
static bool min_cmp(int a, int b) { return a < b; }

Or, if you only ever need one and want zero indirection cost, negate the keys on the way in and out.

Which one to use. A min heap is what you want for a scheduler or timer queue, because the interesting event is the one with the earliest deadline or the smallest virtual runtime. A max heap is what heapsort uses to produce ascending order, for the reason in Q194.

The two classic uses worth naming

• Kth largest element: keep a min heap of size k. Each new element that exceeds the root replaces it and sifts down. At the end the root is the kth largest. O(n log k) time and O(k) space, which beats sorting when k is small.
• Merging k sorted streams: a min heap holding one element from each stream. Pop the smallest, emit it, push the next from that stream. O(n log k).

---

Q191. What does heapify do and what does it cost?

Say this out loud Heapify, or sift down, restores the heap property at one node assuming both its subtrees are already valid heaps. It compares the node with its children, swaps with the larger child if needed, and repeats downward. O(log n). Build-heap applies it to every internal node from the bottom up and is O(n), not O(n log n).

Sift down

void sift_down(heap_t *h, int i) {
    for (;;) {
        int largest = i;
        int l = lchild(i), r = rchild(i);

        if (l < h->size && h->data[l] > h->data[largest]) largest = l;
        if (r < h->size && h->data[r] > h->data[largest]) largest = r;

        if (largest == i) return;                       /* already correct, stop */

        int t = h->data[i]; h->data[i] = h->data[largest]; h->data[largest] = t;
        i = largest;                                    /* follow the element down */
    }
}

Trace. Array [10, 50, 40, 30, 20], sift down from index 0:

        10                    50                    50
      /    \               /     \               /     \
    50      40    -->    10       40    -->    30       40
   /  \                 /  \                  /  \
  30   20             30    20              10    20

step 1: children of 10 are 50 and 40. Largest is 50, swap.
step 2: 10 is now at index 1, children are 30 and 20. Largest is 30, swap.
step 3: 10 is at index 3, no children. Done.

Sift up, used by insert:

void sift_up(heap_t *h, int i) {
    while (i > 0 && h->data[i] > h->data[parent(i)]) {
        int p = parent(i);
        int t = h->data[i]; h->data[i] = h->data[p]; h->data[p] = t;
        i = p;
    }
}

Build heap, and the O(n) proof that is the real question

void build_heap(heap_t *h) {
    for (int i = h->size / 2 - 1; i >= 0; i--) {   /* last internal node, downward */
        sift_down(h, i);
    }
}

Starting at size/2 - 1 skips every leaf, because leaves are already valid heaps of one element. That is half the array skipped for free.

Why it is O(n) and not O(n log n). The naive bound says n nodes times O(log n) each. But almost all nodes are near the bottom, where sift down travels almost no distance.

Total work is n * sum(k / 2^(k+1)) for k from 0 upward. That sum converges to 1, so the total is O(n). The nodes that could travel far are the rare ones near the top, and the many nodes near the bottom barely move.

Being able to give that table and say “the sum converges” is a strong answer. It is one of the few places where the obvious bound is genuinely loose.

The consequence: building a heap from an array is O(n), which is why heapsort’s setup phase is cheaper than its sorting phase.

---

Q192. How do you insert into a heap?

Say this out loud Append the new element at the end of the array, which preserves completeness, then sift it up until its parent is larger. O(log n) worst case.

bool heap_insert(heap_t *h, int v) {
    if (h->size >= HEAP_MAX) return false;      /* fixed capacity: report, do not grow */
    h->data[h->size] = v;
    sift_up(h, h->size);
    h->size++;
    return true;
}

Trace. Insert 60 into [50, 30, 40, 10, 20]:

append at index 5:
        50                     50                    60
      /    \                 /    \                /    \
    30      40      -->    30      60    -->     30      50
   /  \    /              /  \    /             /  \    /
 10   20  60            10   20  40           10   20  40

60 > its parent 40, swap.
60 > its new parent 50, swap.
60 is at the root, stop.

Two swaps for six elements. In a heap of a million elements the maximum is 20.

Why appending is correct. The next free array slot is exactly the next position in the complete tree’s fill order, so completeness is maintained automatically with no reasoning required. That is a second benefit of the array representation.

Average case is better than worst case. Half the nodes are leaves, so a randomly valued insert usually stops after one or two comparisons. The amortized cost of inserting n elements one at a time is O(n) in practice, though the worst case per insert remains O(log n).

---

Q193. How do you extract the root from a heap?

Say this out loud Take the root as the result, move the last element into the root position, shrink the size, and sift that element down. O(log n).

bool heap_extract_max(heap_t *h, int *out) {
    if (h->size == 0) return false;

    *out = h->data[0];                    /* the answer */
    h->data[0] = h->data[h->size - 1];    /* last element becomes the new root */
    h->size--;
    sift_down(h, 0);
    return true;
}

Why the last element and not one of the children. Promoting a child would leave a hole in the middle of the tree and break completeness, so the array indexing would stop working. Moving the last element keeps the shape valid immediately, and the order rule is then repaired by one sift down.

Trace. Extract from [60, 30, 50, 10, 20, 40]:

result is 60.
move 40 (the last) to the root, size becomes 5:

        40                     50
      /    \                 /    \
    30      50     -->     30      40
   /  \                   /  \
 10   20                10   20

children of 40 are 30 and 50. Largest is 50, swap.
40 at index 2 has no children now. Done.

Deleting an arbitrary element, which is the follow up:

void heap_delete_at(heap_t *h, int i) {
    h->data[i] = h->data[h->size - 1];
    h->size--;
    if (i < h->size) {
        sift_down(h, i);
        sift_up(h, i);          /* the replacement may be too LARGE for this position */
    }
}

Both directions are needed, because the element moved in from the end could be smaller than the children, requiring a sift down, or larger than the parent, requiring a sift up. Only one of the two will actually do work, but you cannot know which in advance.

The problem with arbitrary deletion. Finding element i costs O(n), because a heap gives no search structure. That is why priority queues supporting cancellation, such as a timer queue where a timer can be stopped, must store each element’s current index inside the element itself and update it on every swap. That index-back-reference is the standard solution and mentioning it shows practical experience.

---

Q194. How does heap sort work and when do you choose it?

Say this out loud Build a max heap from the array in O(n), then repeatedly swap the root with the last unsorted element and sift down over the shrinking heap. O(n log n) in all cases, in place with O(1) extra space, and not stable.

static void sift_down_n(int *a, int n, int i) {
    for (;;) {
        int largest = i, l = 2*i + 1, r = 2*i + 2;
        if (l < n && a[l] > a[largest]) largest = l;
        if (r < n && a[r] > a[largest]) largest = r;
        if (largest == i) return;
        int t = a[i]; a[i] = a[largest]; a[largest] = t;
        i = largest;
    }
}

void heap_sort(int *a, int n) {
    for (int i = n/2 - 1; i >= 0; i--) sift_down_n(a, n, i);   /* build, O(n) */

    for (int end = n - 1; end > 0; end--) {
        int t = a[0]; a[0] = a[end]; a[end] = t;               /* largest to the back */
        sift_down_n(a, end, 0);                                /* restore over the rest */
    }
}

Why a max heap gives ascending order. The root is the largest remaining element, and you swap it to the end of the unsorted region. The sorted portion grows from the right, filled with progressively smaller values, so the final array is ascending. Using a min heap here would produce descending order.

Trace on [4, 10, 3, 5, 1]

build heap:
  i=1: sift down 10, children 5 and 1, already largest -> no change
  i=0: sift down 4, children 10 and 3, swap with 10
       then 4 at index 1, children 5 and 1, swap with 5
  heap: [10, 5, 3, 4, 1]

extract phase:
  swap a[0] and a[4]:  [1, 5, 3, 4 | 10]   sift over first 4 -> [5, 4, 3, 1 | 10]
  swap a[0] and a[3]:  [1, 4, 3 | 5, 10]   sift -> [4, 1, 3 | 5, 10]
  swap a[0] and a[2]:  [3, 1 | 4, 5, 10]   sift -> [3, 1 | 4, 5, 10]
  swap a[0] and a[1]:  [1 | 3, 4, 5, 10]

result: [1, 3, 4, 5, 10]

The properties table, which is why it matters for firmware

Why heap sort is the right choice for hard real time. Quick sort can degrade to O(n squared). Merge sort needs O(n) extra memory. Heap sort has a guaranteed O(n log n) bound, uses no extra memory, and uses no recursion, so it has no stack depth risk. When you must state a worst case number in a design document, heap sort is the sort that lets you do it. In practice it is roughly two to three times slower than quick sort on typical data because of the cache behaviour, and that is the trade you are making.

---

Q195. How does a heap implement a priority queue?

Covered from the queue side in Q142. The heap-specific view:

When a heap is the right choice is when the number of distinct priorities is large or continuous, such as timestamps or deadlines.

When the bucket approach from Q142 is better is when priorities come from a small fixed set, such as 8 or 32 RTOS priority levels. Then an array of FIFOs plus a CLZ on a ready mask makes everything O(1) and deterministic, which beats O(log n) for a scheduler.

Stating both, and the condition that selects between them, is the complete answer.

Stability. A plain heap is not stable, so two items with equal priority can come out in either order. If FIFO order within a priority matters, and for a scheduler it usually does, store a monotonically increasing sequence number alongside the priority and compare it as a tiebreaker.

---

Q196. What are the time complexities of heap operations?

The two rows that get asked about most

Build is O(n), inserting n times is O(n log n). The difference is the argument in Q191. If you have all the data up front, always build rather than insert repeatedly.

Finding the minimum in a max heap is O(n). Candidates often assume it is at the end of the array. It is somewhere in the leaves, which is the last n/2 entries, but which one is unknown, so you scan them. Answering “O(n), but only over the last half of the array” is the precise version.

---

Q197. How do you build a timer scheduler on a min heap?

Say this out loud A min heap keyed by deadline or next-run time. The root is always the next event to fire, so the tick handler only examines data[0], which is O(1). Adding a timer is O(log n) and firing one is O(log n).

typedef struct {
    uint32_t expiry_tick;
    void   (*callback)(void *);
    void    *arg;
    uint32_t period;              /* 0 means one shot */
    int      heap_index;          /* self reference, so cancel is O(log n) not O(n) */
} timer_t;

typedef struct {
    timer_t *heap[MAX_TIMERS];    /* min heap ordered by expiry_tick */
    int      count;
} timer_queue_t;

/* called from the tick ISR or a timer task */
void timer_tick(timer_queue_t *q, uint32_t now) {
    while (q->count > 0 && q->heap[0]->expiry_tick <= now) {
        timer_t *t = q->heap[0];
        heap_pop(q);
        t->callback(t->arg);
        if (t->period) {
            t->expiry_tick = now + t->period;
            heap_push(q, t);          /* reschedule a periodic timer */
        }
    }
}

The heap_index field is the design point. Every swap inside sift up and sift down must update it:

static void heap_swap(timer_queue_t *q, int i, int j) {
    timer_t *t = q->heap[i]; q->heap[i] = q->heap[j]; q->heap[j] = t;
    q->heap[i]->heap_index = i;
    q->heap[j]->heap_index = j;
}

Without it, cancelling a timer requires an O(n) search to find where it lives. With it, cancellation is O(log n) and, more importantly, bounded. In a system with hundreds of timers that is the difference between a usable and an unusable design.

Heap versus sorted linked list for timers

FreeRTOS uses a sorted list, not a heap, because with a modest timer count the O(n) insert is small and the O(1) removal on every tick is what runs most often. Linux uses a timer wheel for most timers and a red-black tree for high resolution ones. Knowing that different systems make different choices, and being able to explain why, is worth more than defending one structure.

The timer wheel, worth naming. Buckets indexed by expiry % wheel_size, giving O(1) insert and O(1) tick processing at the cost of a cascade step when timers wrap around. It is the right answer when you have thousands of timers and most are cancelled before they fire, which is exactly the network stack case.

---

Q198. Where are heaps used in embedded systems?

The firmware advantages worth stating together:

• Zero pointer overhead, since the array representation stores only the data.
• Fixed capacity known at build time, so the memory appears in the linker map.
• No allocation and no fragmentation.
• No recursion, so no stack depth risk, provided you write sift down iteratively.
• All operations bounded by O(log n), which for 1000 timers is 10 steps.

The disadvantages to acknowledge:

• No search. Locating an arbitrary element is O(n) without an index back reference.
• Poor cache behaviour, because sift down jumps by powers of two through the array. On a Cortex M with no cache this costs nothing, and on an M7 or an A series core it is measurable.
• Not stable, so equal priorities need an explicit tiebreaker.

---

Section 12: Sorting

---

Q199. How does bubble sort work and is it ever the right choice?

Say this out loud Repeatedly walk the array swapping adjacent out-of-order pairs. Each pass bubbles the largest remaining element to the end. O(n squared) in general, but with an early exit flag it is O(n) on already sorted input, which is its one redeeming property.

void bubble_sort(int *a, int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {     /* -i : the tail is already sorted */
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j+1]; a[j+1] = t;
                swapped = true;
            }
        }
        if (!swapped) return;                     /* nothing moved: fully sorted */
    }
}

Trace on [5, 1, 4, 2]

pass 1: [1,5,4,2] -> [1,4,5,2] -> [1,4,2,5]     5 is now in place
pass 2: [1,4,2,5] -> [1,2,4,5]                  4 is now in place
pass 3: no swaps, early exit

The two details that matter. The - i in the inner bound, because the last i elements are already final and rechecking them is wasted work. And the swapped flag, which turns the best case from O(n squared) into O(n).

Honest assessment. Bubble sort is never the right answer in production. It is asked because it is the simplest thing to write correctly under pressure, and because the early exit flag and the shrinking inner bound reveal whether you actually thought about it or reproduced it from memory. If asked for the best small-array sort, say insertion sort and explain why, since it does strictly less work on the same inputs.

---

Q200. How does selection sort work and when does it win?

Say this out loud Find the minimum of the unsorted region and swap it into position. Always O(n squared) comparisons regardless of input, but it performs at most n swaps, which is the fewest of any comparison sort.

void selection_sort(int *a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min]) min = j;
        }
        if (min != i) {
            int t = a[i]; a[i] = a[min]; a[min] = t;
        }
    }
}

Trace on [64, 25, 12, 22]

i=0: min is 12 at index 2, swap -> [12, 25, 64, 22]
i=1: min is 22 at index 3, swap -> [12, 22, 64, 25]
i=2: min is 25 at index 3, swap -> [12, 22, 25, 64]

The one place it wins, and it is a firmware place. When a write is far more expensive than a read. Writing to EEPROM or flash costs milliseconds and consumes a limited erase-write cycle budget, while reading is nearly free. Selection sort performs at most n writes where insertion sort may perform O(n squared). If you must sort records in place in EEPROM, selection sort is the correct choice specifically because of the write count. That answer distinguishes you immediately, because it is a real engineering reason rather than a textbook property.

Why it is not stable. Swapping a distant minimum into position can jump one equal element over another. [2a, 2b, 1] becomes [1, 2b, 2a], reversing the two 2s. A linked-list version that moves nodes instead of swapping values can be stable.

---

Q201. Why is insertion sort fast on nearly sorted data?

Say this out loud Take each element and slide it left into its correct place among the already sorted prefix. O(n squared) worst case but O(n) on nearly sorted data, stable, in place, and the fastest option for small arrays, which is why every production sort falls back to it.

void insertion_sort(int *a, int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];          /* shift right, do not swap */
            j--;
        }
        a[j + 1] = key;
    }
}

Shifting rather than swapping is the optimisation. A swap is three assignments. Shifting is one per element moved, plus one final placement. That is roughly a threefold reduction in memory traffic over the naive swap version.

Trace on [12, 11, 13, 5]

i=1, key=11: 12 > 11, shift -> [12,12,13,5], place -> [11,12,13,5]
i=2, key=13: 12 < 13, no shift                        [11,12,13,5]
i=3, key=5 : 13,12,11 all > 5, shift three times   -> [5,11,12,13]

Why it beats everything else for small n. No recursion, no function call overhead, sequential memory access, and a very tight inner loop. The crossover against quick sort is typically somewhere between 10 and 32 elements depending on the core, which is why std::sort switches to insertion sort below 16 and glibc’s qsort does the same.

Using > and not >= in the loop condition is what makes it stable. With >= the loop keeps shifting past equal elements, so the new element ends up before its equals, reversing their order. One character decides stability.

Firmware relevance. This is the sort to write for anything under about 50 elements: a list of active connections, calibration points, a menu ordering. It compiles to a handful of instructions, has no worst case surprise at that size, and needs no stack.

---

Q202. How does merge sort work and what does it cost in memory?

Say this out loud Divide the array in half, sort each half recursively, then merge the two sorted halves. O(n log n) guaranteed in all cases, stable, but it needs O(n) auxiliary memory for the merge. It is the natural sort for linked lists, where the extra memory cost disappears.

static void merge(int *a, int lo, int mid, int hi, int *tmp) {
    int i = lo, j = mid + 1, k = lo;

    while (i <= mid && j <= hi)
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];    /* <= keeps it stable */

    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi)  tmp[k++] = a[j++];

    for (int x = lo; x <= hi; x++) a[x] = tmp[x];
}

void merge_sort(int *a, int lo, int hi, int *tmp) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    merge_sort(a, lo, mid, tmp);
    merge_sort(a, mid + 1, hi, tmp);
    if (a[mid] <= a[mid + 1]) return;     /* already ordered across the boundary, skip */
    merge(a, lo, mid, hi, tmp);
}

That a[mid] <= a[mid+1] check is a free optimisation: if the largest of the left half is already no bigger than the smallest of the right half, the merge would just copy, so skip it. On nearly sorted input this turns the whole sort into O(n).

The recursion tree

                [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]

merge upward:
  [27,38]  [3,43]  [9,82]  [10]
  [3,27,38,43]     [9,10,82]
  [3,9,10,27,38,43,82]

Each level does O(n) total merging work, and there are log n levels, so O(n log n). That picture is the recursion-tree argument from Q87.

Allocating tmp once. Allocating inside merge would call malloc at every level of the recursion. Allocate one buffer at the top and pass it down, or use a static buffer in firmware. That detail is worth pointing out because the naive implementation is a performance and fragmentation disaster.

---

Q203. How does quick sort work and what is its worst case?

Say this out loud Choose a pivot, partition the array so everything smaller is on the left and everything larger on the right, then recurse on both sides. O(n log n) average with excellent constants and in-place operation, but O(n squared) worst case if the pivot choice is poor.

Lomuto partition, easier to write correctly

static int partition_lomuto(int *a, int lo, int hi) {
    int pivot = a[hi];                   /* last element as the pivot */
    int i = lo - 1;                      /* boundary of the "smaller" region */

    for (int j = lo; j < hi; j++) {
        if (a[j] <= pivot) {
            i++;
            int t = a[i]; a[i] = a[j]; a[j] = t;
        }
    }
    int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;   /* pivot into its final place */
    return i + 1;
}

void quick_sort(int *a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition_lomuto(a, lo, hi);
    quick_sort(a, lo, p - 1);
    quick_sort(a, p + 1, hi);
}

Trace of one partition on [7, 2, 1, 6, 8, 5, 3, 4], pivot 4

Pivot 4 is at index 3, with everything smaller to its left. Correct.

Hoare partition, which is what real implementations use because it does about three times fewer swaps:

static int partition_hoare(int *a, int lo, int hi) {
    int pivot = a[lo + (hi - lo) / 2];
    int i = lo - 1, j = hi + 1;
    for (;;) {
        do { i++; } while (a[i] < pivot);
        do { j--; } while (a[j] > pivot);
        if (i >= j) return j;                 /* returns a SPLIT point, not a final index */
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}
/* note the different recursion: quick_sort(a, lo, p); quick_sort(a, p + 1, hi); */

Hoare returns a division point rather than the pivot’s final position, so the recursive calls differ from Lomuto’s. Mixing the two conventions produces an infinite loop, and that is a common bug.

Tail call elimination, which bounds the stack

void quick_sort_bounded(int *a, int lo, int hi) {
    while (lo < hi) {
        int p = partition_lomuto(a, lo, hi);
        if (p - lo < hi - p) {                 /* recurse on the SMALLER side */
            quick_sort_bounded(a, lo, p - 1);
            lo = p + 1;                        /* loop on the larger side */
        } else {
            quick_sort_bounded(a, p + 1, hi);
            hi = p - 1;
        }
    }
}

Always recursing on the smaller partition and looping on the larger bounds the stack depth at O(log n) even in the worst case. That single change makes quick sort acceptable in firmware where the naive version is not, and volunteering it is a strong senior signal.

---

Q204. When do you choose heap sort over quick sort?

Covered fully in Q194. The one-line role: the sort you choose when you must guarantee O(n log n) with O(1) memory and no recursion.

---

Q205. How does counting sort beat O(n log n)?

Say this out loud Not a comparison sort. Count how many times each value occurs, then use a running total to place each element directly at its final index. O(n + k) where k is the range of values, which beats O(n log n) when the range is small. Requires integer keys in a known bounded range.

void counting_sort(int *a, int n, int max_val) {
    int count[max_val + 1];
    memset(count, 0, sizeof count);

    for (int i = 0; i < n; i++) count[a[i]]++;              /* tally */

    for (int i = 1; i <= max_val; i++) count[i] += count[i-1];  /* running total */

    int out[n];
    for (int i = n - 1; i >= 0; i--) {                      /* BACKWARDS, for stability */
        out[--count[a[i]]] = a[i];
    }

    memcpy(a, out, n * sizeof(int));
}

Trace on [4, 2, 2, 8, 3] with max 8

counts:     index: 0 1 2 3 4 5 6 7 8
                   0 0 2 1 1 0 0 0 1

running:           0 0 2 3 4 4 4 4 5

place backwards:
  a[4]=3: count[3] is 3, decrement to 2, out[2]=3
  a[3]=8: count[8] is 5, decrement to 4, out[4]=8
  a[2]=2: count[2] is 2, decrement to 1, out[1]=2
  a[1]=2: count[2] is 1, decrement to 0, out[0]=2
  a[0]=4: count[4] is 4, decrement to 3, out[3]=4

result: [2, 2, 3, 4, 8]

Why the final loop runs backwards. Iterating the input from the end and decrementing the count places the last occurrence of a value at the highest of its output slots, which preserves the original relative order of equal elements. Running forwards would reverse them and break stability. That is the detail interviewers check.

When it is the correct choice in firmware. Sorting ADC readings that are 12 bit, so k is 4096. Sorting bytes, where k is 256 and the count array is 1 KB. Sorting by a small enumerated priority. If k is comparable to n or smaller, this is dramatically faster than any comparison sort, and if k is huge, such as full 32 bit values, the count array is impossible and this is unusable. Stating that condition is the answer.

---

Q206. How does radix sort work?

Say this out loud Sort by one digit at a time, from least significant to most, using a stable sort such as counting sort for each pass. O(d times (n + b)) where d is the number of digits and b is the base. It works because each pass preserves the ordering established by all previous passes, which requires the inner sort to be stable.

void radix_sort(uint32_t *a, int n) {
    uint32_t *out = malloc(n * sizeof *out);

    for (int shift = 0; shift < 32; shift += 8) {     /* 4 passes of 8 bits */
        int count[256] = {0};

        for (int i = 0; i < n; i++) count[(a[i] >> shift) & 0xFF]++;
        for (int i = 1; i < 256; i++) count[i] += count[i-1];
        for (int i = n - 1; i >= 0; i--)
            out[--count[(a[i] >> shift) & 0xFF]] = a[i];

        memcpy(a, out, n * sizeof *a);
    }
    free(out);
}

Trace on [170, 45, 75, 90, 802, 24, 2, 66], base 10

by 1s digit:   170, 90, 802, 2, 24, 45, 75, 66
by 10s digit:  802, 2, 24, 45, 66, 170, 75, 90
by 100s digit: 2, 24, 45, 66, 75, 90, 170, 802

Watch the 10s pass: 802 and 2 both have a 10s digit of 0, and 802 came first from the previous pass, so it stays first. That is stability doing the work. If the inner sort were unstable, the 1s ordering would be destroyed and the result would be wrong.

Choosing the base. Base 256, meaning 8 bits per pass, gives 4 passes for a 32 bit key with a 1 KB count array. Base 65536 gives 2 passes but a 256 KB count array. On a microcontroller, base 16 with 8 passes and a 64 byte count array may be the right point. That is a genuine memory-versus-passes trade you can discuss.

Signed integers and floats need care. Two’s complement negatives have the top bit set, so a straight radix sort places them after positives. Flip the sign bit before sorting and flip it back afterwards. For IEEE floats, flip the sign bit for positives and all bits for negatives, which maps them to a monotonic unsigned ordering. Knowing this exists is a good bonus.

Firmware relevance. Radix sort is the fastest way to sort large sets of fixed-width integer keys, such as timestamps or sensor IDs, and it is used in packet classification. The cost is O(n) extra memory, which often rules it out on small parts.

---

Q207. How does bucket sort work and when does it degrade?

Say this out loud Distribute elements into buckets covering equal sub-ranges of the input, sort each bucket individually, then concatenate. O(n) average when the input is uniformly distributed, O(n squared) when everything lands in one bucket.

void bucket_sort(float *a, int n) {          /* values in [0, 1) */
    bucket_t buckets[n];
    for (int i = 0; i < n; i++) bucket_init(&buckets[i]);

    for (int i = 0; i < n; i++)
        bucket_add(&buckets[(int)(n * a[i])], a[i]);   /* index by value */

    int k = 0;
    for (int i = 0; i < n; i++) {
        insertion_sort_bucket(&buckets[i]);            /* each bucket is small */
        for (int j = 0; j < buckets[i].count; j++) a[k++] = buckets[i].items[j];
    }
}

Why it can beat O(n log n). With uniform input, each of the n buckets holds about one element, so sorting each is O(1) and the total is O(n). The comparison-sort lower bound does not apply because the bucket assignment uses the value directly rather than comparing.

Why it degrades. Skewed input puts everything in one bucket, and you are left running insertion sort on the whole array, which is O(n squared). The distribution assumption is doing all the work, and it is the assumption to state explicitly.

The relationship to the others, which is a good thing to say:

• Counting sort is bucket sort with one bucket per distinct value and no inner sort needed.
• Radix sort is repeated bucket sort, one digit at a time.
• Bucket sort with two buckets and a pivot boundary is essentially one level of quick sort.

Presenting them as a family rather than three unrelated algorithms shows structural understanding.

---

Q208. How does shell sort improve on insertion sort?

Say this out loud Insertion sort applied at decreasing gaps. Sorting elements that are far apart first moves items a long distance cheaply, so by the time the gap reaches 1 the array is nearly sorted and the final insertion pass is close to O(n). Complexity depends on the gap sequence, roughly O(n^1.3) for good sequences.

void shell_sort(int *a, int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {          /* the original Shell sequence */
        for (int i = gap; i < n; i++) {
            int key = a[i];
            int j = i;
            while (j >= gap && a[j - gap] > key) {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = key;
        }
    }
}

Compare with Q201: it is literally insertion sort with 1 replaced by gap, wrapped in a loop that shrinks the gap. Saying that is the fastest way to explain it.

Why the gaps help. Plain insertion sort moves an element one position per operation, so an element that belongs n places away costs n operations. With a gap of n/2, it can travel half the array in a single step. Each pass reduces the number of inversions dramatically, so the final gap-1 pass has very little left to do.

Gap sequences and their bounds

Where it wins, and this is a firmware answer. Shell sort is the sweet spot for medium sized arrays, roughly 50 to 1000 elements, on a memory constrained system. It needs no extra memory, no recursion, and no stack, it is about 40 lines shorter than quick sort with its pivot selection and partition, and it substantially beats insertion sort. Several embedded C libraries use it as their general purpose sort for exactly these reasons. uClibc’s qsort has historically been a shell sort.

---

Q209. Which sorts are stable?

Say this out loud Stable means two elements with equal keys keep their original relative order. It matters whenever you sort by one field after already having sorted by another, because stability is what preserves the earlier ordering.

Why it matters, concretely. Sort log entries by timestamp, then stably sort by severity. The result is grouped by severity with each group still in timestamp order. With an unstable sort the timestamp ordering inside each group is destroyed and you must sort by a composite key instead.

Making an unstable sort stable. Append the original index as a tiebreaker in the comparison. This always works and costs O(n) extra memory for the indices, which is why it is not the default.

The gotcha to know: std::sort is not stable. std::stable_sort is, and it uses merge sort with a temporary buffer, falling back to a slower in-place merge if allocation fails. C’s qsort is not guaranteed stable either. Knowing which library functions guarantee stability is a standard checkpoint.

---

Q210. Which sorts are in place?

Say this out loud In place means O(1) or O(log n) auxiliary space, not counting the input array. The distinction that matters for firmware is whether the algorithm needs a second array of size n, because on a part with 32 KB of RAM that decides whether you can sort 4000 integers at all.

The convention argument. Quick sort uses O(log n) stack for recursion, so strictly it is not O(1). It is conventionally called in place because it needs no auxiliary array, and O(log n) for a million elements is 20 frames. Stating the convention rather than arguing about it is the right move.

In-place merge sort exists but the in-place merge is O(n log n) by itself, making the whole sort O(n log squared n), and the constants are bad. It is a curiosity rather than a tool.

---

Q211. What is the worst case for each sorting algorithm?

The row that matters is quick sort. Choosing the first or last element as the pivot makes already sorted input the worst case, which is the input you are most likely to encounter in practice. Every partition splits off one element, giving n levels of recursion at O(n) work each.

Worse, the recursion depth becomes O(n), so on a target you get a stack overflow rather than merely a slow sort. Mitigations are in Q216 and the tail-elimination trick in Q203.

The security angle worth mentioning. An attacker who knows your pivot rule can construct input that forces O(n squared), which is a denial of service against any service that sorts untrusted input. This was a real vulnerability class in language runtimes, and randomised pivots or introsort are the fix.

---

Q212. What is the best case for each sorting algorithm?

Adaptive sorts are the ones that exploit existing order: insertion, bubble with the flag, shell, and Timsort. Selection and heap sort are not adaptive at all, and doing nothing useful with sorted input is a real weakness for data that is usually nearly sorted, which describes most real data.

The practical consequence. Sensor readings, timestamps, and log entries usually arrive nearly sorted. Insertion sort on that data is close to O(n) and beats quick sort’s O(n log n) for surprisingly large n. If you know your data is nearly sorted, say so and pick accordingly.

---

Q213. What is the average case for each sorting algorithm?

The point interviewers want. All three of merge, quick, and heap are O(n log n) on average, yet quick sort is typically two to three times faster in practice. Big O hides the constant, and here the constant is dominated by cache behaviour: quick sort’s partition is a sequential scan from both ends, while heap sort’s sift down jumps by powers of two and merge sort copies the whole array at every level.

Saying “they are all O(n log n) but quick sort has the best constant because its memory access is sequential” is a much stronger answer than reciting the complexities.

The comparison sort lower bound. Any sort that only compares elements needs at least log2(n!), which is about n log n, comparisons in the worst case. The argument is that there are n! possible orderings and each comparison distinguishes at most two branches, so the decision tree has depth at least log2(n!). This is why counting and radix sort, which do not compare, can be O(n): they use the key’s structure rather than comparisons.

---

Q214. Which sort for embedded?

Say this out loud It depends on three things: the array size, whether extra memory is available, and whether a worst case bound must be provable. My defaults are insertion sort below about 50 elements, shell sort or heap sort for medium arrays with no spare memory, counting or radix sort if the keys are small integers, and heap sort whenever a hard real time guarantee is required.

The decision table

What to avoid on a target, and why

• Plain quick sort with a first-element pivot. Sorted input gives O(n squared) time and O(n) stack depth, which is a crash, not a slowdown.
• Recursive merge sort with malloc inside the merge. An allocation at every level, and it can fail partway through.
• Library qsort. It is a function-pointer comparison per element, so it cannot inline the comparison, and its implementation varies between C libraries with no guarantee on stack usage. A hand written insertion or shell sort for your specific type is smaller and faster.

The sentence that lands well: on a target I care more about the worst case and the memory than about the average case, so I will accept heap sort being twice as slow as quick sort in exchange for being able to write a bound in the design document.

---

Q215. Why does merge sort need extra memory?

Say this out loud Because merging two sorted runs in place is fundamentally hard. Placing an element from the right run into its correct position among the left run requires shifting everything between, which costs O(n) per element. The temporary array lets you write each merged element exactly once, keeping the merge at O(n).

The concrete demonstration

left:  [1, 3, 5]      right: [2, 4, 6]      merging in place

To place 2 after 1, you must shift 3 and 5 right by one. Then to place 4 you shift 5. Each insertion is O(n), and n insertions make the merge O(n squared), which destroys the whole point of the algorithm.

With a temporary buffer, you simply walk both runs and append the smaller each time. One write per element, O(n) total.

How much extra. A single buffer of n elements, allocated once at the top and reused at every level. The naive implementation allocating inside merge is what makes people think merge sort needs O(n log n) memory, which it does not.

Why the linked list version needs none. Merging lists rewires pointers instead of copying values, so there is no shifting and no buffer. The only extra space is O(log n) for the recursion.

node_t *merge_sort_list(node_t *head) {
    if (!head || !head->next) return head;
    node_t *mid = split_in_half(head);            /* slow and fast pointer, Q104 */
    return merge_sorted(merge_sort_list(head), merge_sort_list(mid));   /* Q109 */
}

That is why merge sort is the standard sort for linked lists, and it is exactly what std::list::sort does.

The firmware consequence. Sorting 4000 uint32_t values with merge sort needs 16 KB for the array and another 16 KB for the buffer. On a part with 32 KB of RAM that does not fit alongside everything else. Heap sort sorts the same array with zero extra bytes. That arithmetic is the answer to why heap sort exists.

---

Q216. How do you choose a quick sort pivot?

Say this out loud The pivot decides everything. First or last element gives O(n squared) on sorted input, which is the most common real input. Median of three is the standard fix and is cheap. Randomised pivots defeat adversarial input. Median of medians gives a true O(n) guarantee but its constant is too large to be worth it.

static int median_of_three(int *a, int lo, int hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] < a[lo])  swap(&a[mid], &a[lo]);
    if (a[hi]  < a[lo])  swap(&a[hi],  &a[lo]);
    if (a[hi]  < a[mid]) swap(&a[hi],  &a[mid]);
    return mid;                                   /* a[mid] is now the median */
}

This sorts the three sampled positions as a side effect, which is a small bonus, and it makes already-sorted input the best case rather than the worst, since the middle element of a sorted array is the perfect pivot.

The three-way partition, for arrays with many duplicates

Standard quick sort degrades badly when many elements equal the pivot, because they all pile into one partition. Dutch national flag partitioning splits into three regions, less than, equal to, and greater than, and recurses only on the outer two.

[ < pivot | == pivot | > pivot ]

An array of all identical values becomes O(n) instead of O(n squared). If the interviewer mentions duplicates, this is the expected answer.

---

Q217. What is hybrid sorting and why does introsort exist?

Say this out loud Real implementations combine algorithms to get each one’s best property. Introsort starts with quick sort, switches to heap sort when the recursion gets too deep, and finishes with insertion sort on small ranges. Timsort combines merge sort with insertion sort and detects existing sorted runs.

Introsort, which is what std::sort is

void introsort(int *a, int lo, int hi, int depth_limit) {
    while (hi - lo > 16) {                        /* 1. small ranges: leave for insertion */
        if (depth_limit == 0) {
            heap_sort_range(a, lo, hi);           /* 2. too deep: switch to heap sort */
            return;
        }
        depth_limit--;
        int p = partition(a, lo, hi);
        introsort(a, p + 1, hi, depth_limit);     /* recurse on one side */
        hi = p;                                    /* loop on the other, bounding the stack */
    }
    /* fall through: the array is now "nearly sorted" in 16-element blocks */
}

void sort(int *a, int n) {
    introsort(a, 0, n - 1, 2 * ilog2(n));
    insertion_sort(a, n);                          /* 3. one final near-linear pass */
}

Why each piece is there

That last point is subtle and worth stating: leaving the small blocks unsorted and doing a single insertion pass at the end is faster than sorting each block individually, because insertion sort on nearly-sorted data is O(n) and you pay the loop overhead once.

Timsort, used by Python and Java for objects, finds naturally occurring sorted runs, extends short ones with insertion sort, and merges runs using a stack with balance invariants. It is O(n) on already sorted input and stable. It is complex, but knowing why it exists, real data usually contains sorted runs, is the useful part.

The takeaway for the interview: no single sort is best. Production sorts are hybrids because worst case protection, small-array efficiency, and average speed are three different requirements.

---

Q218. What algorithms do std::sort and std::stable_sort use?

std::sort versus C qsort, which is the question behind the question

std::sort is typically two to three times faster, for one reason: the comparator is a template parameter, so the compiler inlines it. qsort takes a function pointer, so every single comparison is an indirect call that cannot be inlined, cannot be optimised across, and costs a branch predictor slot.

For n elements there are about n log n comparisons, so at a million elements that is 20 million indirect calls versus 20 million inlined instructions. That is the entire difference, and it is a good concrete example of why C++ templates are described as zero cost abstraction.

The std::sort guarantee changed. Before C++11 the standard only required O(n log n) average. C++11 tightened it to O(n log n) worst case, which is precisely why implementations adopted introsort.

Embedded relevance. On a target, neither is usually the right answer. Both drag in code you may not want, std::sort instantiates a template per type which grows flash, and qsort has unspecified stack usage. For a known type and a known size range, a hand written insertion or shell sort is smaller, faster, and has a stack usage you can measure. Saying that, while demonstrating that you know exactly what the library does, is the strongest possible answer.

---

Master comparison table

---

Quick revision sheet, questions 189 to 218

---

---

All seven parts of the guide

• Part 1: C Fundamentals, Pointers and Memory — Q1 to Q35
• Part 2: Arrays and Strings — Q36 to Q73
• Part 3: Recursion and Linked Lists — Q74 to Q123
• Part 4: Stack and Queue — Q124 to Q153
• Part 5: Trees and Binary Search Trees — Q154 to Q188
• Part 6: Heap and Sorting — Q189 to Q218 (you are here)
• Part 7: Hashing and Complexity — Q219 to Q248

Start here: The Embedded Firmware DSA Interview Guide, all 248 questions indexed in one place. Architecture round: Firmware Architecture Interview Questions: 100 Q&A.

---

Work with us

Kalapi Infotech builds firmware for connected embedded products — architecture and BSP work, RTOS and bare-metal development, secure boot and OTA infrastructure. If you are hiring for these roles, or building a product that needs them, we would be glad to talk.

Get in touch with our firmware team →