Which sorting algorithm would you use on a microcontroller?
Short answer: It depends on n, memory and timing requirements. Insertion sort for small (n below ~20–30) or nearly sorted arrays: simple, in-place, stable and fastest in practice for tiny inputs. Heap sort when you need guaranteed O(n log n) with O(1) extra memory and no recursion. Quicksort is fastest on average but has an O(n²) worst case and uses recursion (stack); use median-of-three pivots and recurse on the smaller half if you use it. Merge sort is stable and O(n log n) but needs O(n) extra memory. Counting or radix sort for small integer keys (e.g. 8- or 12-bit ADC values) in O(n + k).
#include <stdio.h>
#include <stddef.h>
void insertion_sort(int *a, size_t n)
{
for (size_t i = 1; i < n; i++) {
int key = a[i];
size_t j = i;
while (j > 0 && a[j - 1] > key) { a[j] = a[j - 1]; j--; }
a[j] = key;
}
}
int main(void)
{
int a[] = { 7, 3, 9, 1, 4, 1, 8 };
insertion_sort(a, 7);
for (int i = 0; i < 7; i++) printf("%d ", a[i]); /* 1 1 3 4 7 8 9 */
printf("\n");
return 0;
}
Typical embedded sorting problems and good answers
| Problem | Good choice |
|---|---|
| Median filter of 5–9 samples (remove spikes) | insertion sort of a copy, or a sorting network |
| Sort 1000 16-bit sensor readings | radix/counting sort or heap sort |
| Keep the top-k largest values | min-heap of size k, O(n log k) |
| Nearly sorted log entries by timestamp | insertion sort |
| Must be stable and n is large | merge sort with a static scratch buffer |
| Standard library available, non-critical code | qsort (check its stack usage and that its worst case is acceptable) |
Hard real-time: prefer algorithms whose worst case is acceptable and bounded (heap sort, fixed sorting networks) over ones that are fast "on average".
Sorting networks: fixed sequences of compare-and-swap operations for a known small n (for example, 19 compare-swaps give the median of 9 values); branch-free and constant time, used in DSP median filters.