Quicksort with standard optimizations

qs.c

#include <stdio.h>
#include <stdlib.h>

static int med3(int a, int b, int c) {
  return a < b
    ? c < a ? a : (c < b ? c : b)
    : c > a ? a : (c > b ? c : b);
}

static void swap(int *a, int i, int j) {
  int t = a[i]; a[i] = a[j]; a[j] = t;
}

// Quicksort with median 3 pivot, Dutch national flag partition, and O(log n) stack
void sort(int *a, int n) {
  while (n > 1) {
    // Non-standard choices for median 3 avoid bad behavior on sorted input.
    int mid = med3(a[n / 4], a[n / 2], a[3 * n / 4]);
    int i = 0, j = 0, k = n - 1;
    while (j <= k)
      if (a[j] < mid) swap(a, i++, j++);
      else if (a[j] > mid) swap(a, j, k--);
      else j++;
    if (i < n - j) {
      sort(a, i);
      a += j; n -= j;
    } else {
      sort(a + j, n - j);
      n = i;
    }
  }
}

int main(void) {
  int n = 1000000, a[n];
  for (int i = 0; i < n; ++i) a[i] = random() % 1000;
  sort(a, n);
  for (int i = 0; i < n; ++i) printf("%d\n", a[i]);
  return 0;
}