All three are O(n log n) average, but their worst cases and memory differ in ways that matter on an MCU. Quicksort: O(n log n) average and in-place, but O(n²) worst case on bad pivots (e.g. already-sorted input with a naive pivot) and uses O(log n)-O(n) recursion stack, a stack-overflow risk on a small MCU with adversarial input; usable with median-of-three pivots and depth limits (introsort), but riskier on bare metal with untrusted data. Mergesort: guaranteed O(n log n) and stable, but needs O(n) scratch memory to merge, frequently the dealbreaker on a RAM-starved part. Heapsort: O(n log n) worst case and O(1) space (in-place), which makes it the strongest pick when you need a bounded worst case with no scratch memory, at the cost of not being stable and having poor cache locality. So on embedded: heapsort for large n with hard WCET and tight RAM, mergesort when you have the RAM and need stability/bounded time, and quicksort mostly on hosts or where you can guarantee good pivots. And for small n, none of them, insertion sort.
Data Structures & Algorithms · Interview question
Compare quicksort, mergesort, and heapsort for an embedded context.
A strong answer
What a weak answer sounds like
You know the answer. Do you know what gets you dinged?
Pro breaks down the answer most candidates actually give to this question — and the specific reason an interviewer marks it down. It’s the difference between sounding correct and sounding senior, on all 472 questions.
From the lesson
Sorting Basics
The O(n²) simple sorts vs the O(n log n) fast ones, and why on embedded the simple, in-place insertion sort often beats the asymptotically-better choice at small n.