JdBP>> Whenever I need to code a sort of my own (as opposed to just using 
 JdBP>> qsort()) I use Comb Sort.  It's reasonably fast, and it is
 JdBP>> uncomplicated and small  enough that it is easy to remember.
 MB> what is the comb sort? 
Comb sort is a variation on bubble sort that doesn't sort adjacent elements, 
but instead traverses the array using a progressively narrower gap width 
between compared elements.  The authors likened it to combing the array with 
a set of combs with progressively finer teeth.
The idea is to combat the weaknesses of Bubble Sort (it takes a long time for 
elements to "bubble up" the array if they are far from their final position) 
without complicating the underlying concept too much.  Although the algorithm 
is still O(N*N), it is at least as fast as Bubble Sort in the best case, and 
a lot faster than Bubble Sort in the worst.
#include 
#include 
#include "_stdlib.h"
//
// Speedy version of bubble sort using variable gap sizes
//
void    
Combsort ( void *base,
    size_t num,
    size_t width,
    int (*compare)(const void *, const void *) )
{
 size_t gap = num;
 unsigned char swapped = 0;
 do {
  if (gap > (UINT_MAX / 10))
   gap = (gap / 13) * 10 ;
  else
   gap = (gap * 10) / 13 ;
  if (gap == 0) {
   // When the gap is less than one, we just turn 
                        // into the bubble sort.
   gap = 1 ;
  } else if (gap == 9 || gap == 10) {
   // There are three ways that the gap can go 
                        // near the end :
   //          9 6 4 3 2 1
   //         10 7 5 3 2 1
   //         11 8 6 4 3 2 1
   // The last is the best for our purposes
   gap = 11 ;
  }
  swapped = 0 ;
  char * e1 = (char *)base ;
  char * e2 = e1 + (width * gap) ;
  for (size_t i = num - gap ; i-- ; ) {
   if ((*compare)(e1, e2) > 0) {
    char *p = e1, *q = e2 ;
    for (size_t j = width ; j-- ; ) {
     char hold = *p ;
     *p++ = *q ;
     *q++ = hold ;
    }
    swapped = 1 ;
   }
   e1 += width ;
   e2 += width ;
  }
 } while (swapped || (gap > 1)) ;
}
 ¯ JdeBP ®
--- FleetStreet 1.19 NR
---------------