</>EmbeddedInterview

Implement quicksort.

Medium"Coding: Sorting & Array Problems"
#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.