Sort an array of 0s, 1s and 2s (Dutch national flag).
#include <stddef.h>
void sort012(int *a, size_t n)
{
size_t lo = 0, mid = 0, hi = n; /* [0,lo)=0, [lo,mid)=1, [mid,hi)=unknown, [hi,n)=2 */
while (mid < hi) {
if (a[mid] == 0) { int t = a[lo]; a[lo++] = a[mid]; a[mid++] = t; }
else if (a[mid] == 1) { mid++; }
else { hi--; int t = a[hi]; a[hi] = a[mid]; a[mid] = t; } /* don't advance mid */
}
}
/* {2, 0, 2, 1, 1, 0} -> {0, 0, 1, 1, 2, 2} */
Points: one pass, O(n), O(1) space, using three regions. After swapping a 2 to the end, do not advance mid, because the element swapped in has not been examined yet. Counting sort (count 0s, 1s, 2s, then rewrite) also works in two passes.