A long time ago I came across an article in BYTE magazine (April 1991) about some medical doctors (really) who figured out a great improvement to bubble sort by trial and error.
The COMB sort is similar to the Shell Metzner in that is compares items in the array that are separated by a 'GAP'.
The difference is in how you calculate the GAP.
Comb sort uses a magic value of 1.3. Each time through the array, the GAP is divided by 1.3.
This gives an amazing improvement over BUBBLE sort with only a couple of extra lines of code
And the bigger the array the better the improvement, but even on 32 chars it is 10X faster. :-)
I have provided two simple DEMO programs that sort characters on the screen for anyone who might need a sort routine.
Bubble sort demo