Dr. Dobb's Journal November 1998
void ssort(char *a[], int n, int depth)
{ int le, lt, gt, ge, r, v;
if (n <= 1)
return;
swap(a, 0, rand() % n);
v = ch(0);
le = lt = 1;
gt = ge = n-1;
for (;;) {
for ( ; lt <= gt && ch(lt) <= v; lt++)
if (ch(lt) == v)
swap(a, le++, lt);
for ( ; lt <= gt && ch(gt) >= v; gt--)
if (ch(gt) == v)
swap(a, gt, ge--);
if (lt > gt)
break;
swap(a, lt++, gt--);
}
r = min(le, lt-le);
vecswap(a, 0, lt-r, r);
r = min(ge-gt, n-ge-1);
vecswap(a, lt, n-r, r);
ssort(a, lt-le, depth);
if (v != 0)
ssort(a + lt-le, le + n-ge-1, depth+1);
ssort(a + n-(ge-gt), ge-gt, depth);
}