Implement quicksort.
#include <stddef.h>
static void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }
/* Lomuto partition with median-of-three pivot */
static size_t partition(int *a, size_t lo, size_t hi) /* inclusive bounds */
{
size_t 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[mid] < a[hi]) swap(&a[mid], &a[hi]); /* median now at a[hi] */
int pivot = a[hi];
size_t i = lo;
for (size_t j = lo; j < hi; j++)
if (a[j] < pivot) swap(&a[i++], &a[j]);
swap(&a[i], &a[hi]);
return i;
}
void quick_sort(int *a, size_t lo, size_t hi)
{
while (lo < hi) {
size_t p = partition(a, lo, hi);
if (p - lo < hi - p) { /* recurse on the smaller side */
if (p > lo) quick_sort(a, lo, p - 1);
lo = p + 1; /* loop on the larger side */
} else {
quick_sort(a, p + 1, hi);
if (p == 0) break;
hi = p - 1;
}
}
}
/* usage: if (n > 1) quick_sort(a, 0, n - 1); */
Points: average O(n log n), worst O(n²) (already sorted input with a naive pivot; median-of-three helps), in place, not stable. Recursing only on the smaller part bounds stack depth to O(log n), which matters on a microcontroller. qsort() from the C library is usually fine in practice, but its timing is not deterministic.