Sorting Strings with Three-Way Radix Quicksort

Sorting Strings with Three-Way Radix Quicksort

By Jon Bentley and Robert Sedgewick

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

Example 2: C program to sort strings.