Algorithm Alley
by Jon Bentley and Robert Sedgewick

Example 1: 

void iqs(int a[], int n) 
{   int le, lt, gt, ge, r, v;
    if (n <= 1)
         return;
    swap(a, 0, rand() % n);
    v = a[0];
    le = lt = 1;
    gt = ge = n-1;
    for (;;) {
        for ( ; lt <= gt && a[lt] <= v; lt++)
            if (a[lt] == v)
                swap(a, le++, lt);
        for ( ; lt <= gt && a[gt] >= v; gt--)
                if (a[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);
        iqs(a, lt-le);
        iqs(a + n-(ge-gt), ge-gt); 
} 

Example 2: 

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); 
} 


Listing One 
/* THREE-WAY RADIX QUICKSORT */

/* Support functions */

#ifndef min 
#define min(a, b) ((a)<=(b) ? (a) : (b)) 
#endif

void swap(char *a[], int i, int j) 
{     char *t = a[i];
      a[i] = a[j];
      a[j] = t; 
}
void vecswap(char *a[], int i, int j, int n) 
{     while (n-- > 0)
         swap(a, i++, j++); 
}

/* Simple version */
#define ch(i) a[i][depth]
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); 
}
void ssortmain(char *a[], int n) 
{    ssort(a, n, 0); } 

/* Faster version */
int med3func(char *a[], int ia, int ib, int ic, int depth) 
{   int va, vb, vc;
    if ((va=ch(ia)) == (vb=ch(ib)))
         return ia;
    if ((vc=ch(ic)) == va || vc == vb)
         return ic;
    return va < vb ?
        (vb < vc ? ib : (va < vc ? ic : ia ) )
        : (vb > vc ? ib : (va < vc ? ia : ic ) ); } 
#define med3(ia, ib, ic) med3func(a, ia, ib, ic, depth)
void inssort(char *a[], int n, int depth) 
{   int i, j;
    for (i = 1; i < n; i++)
      for (j = i; j > 0; j--) {
         if (strcmp(a[j-1]+depth, a[j]+depth) <= 0)
             break;
         swap(a, j, j-1);
      } 
} 
void ssort2(char *a[], int n, int depth) 
{    int le, lt, gt, ge, r, v;
     int pl, pm, pn, d;
     if (n <= 10) {
        inssort(a, n, depth);
        return;
     }
     pl = 0;
     pm = n/2;
     pn = n-1;
     if (n > 50) {
        d = n/8;
        pl = med3(pl, pl+d, pl+2*d);
        pm = med3(pm-d, pm, pm+d);
        pn = med3(pn-2*d, pn-d, pn);
     }
     pm = med3(pl, pm, pn);
     swap(a, 0, pm);
     v = ch(0);
     for (le = 1; le < n && ch(le) == v; le++)
       ;  
     if (le == n) {
         if (v != 0)
            ssort2(a, n, depth+1);
         return;
     }
     lt = le;
     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);
         ssort2(a, lt-le, depth);
         if (v != 0)
             ssort2(a + lt-le, le + n-ge-1, depth+1);
         ssort2(a + n-(ge-gt), ge-gt, depth); 
} 
void ssort2main(char *a[], int n) 
{ ssort2(a, n, 0); }


4