How To (Slowly) Sort A List

Have any algorithms been studied as extensively as sorting algorithms?

Indeed, Donald Knuth’s seminal [I don’t think I’ve ever used that word before!] “The Art of Computer Programming” has an entire volume dedicated to sorting and searching.

Most computer programs give you options for sorting info in whatever format they use. Most programming environments provide sorting routines. However, I’ve often found that little, odd, practical details require custom sorting routines. In fact, thinking about it recently, it occurred to me that I may have implemented sort routines more than any other algorithms.

My favorite sort is the Postman’s sort. It’s very simple and very anthropomorphic. And it uses no comparisons! However the actual details of implementing a Postman’s sort usually get more complicated than the algorithm itself, so I almost never use it.

The fastest sort I’ve ever used was some recursive method I found in a Lisp or Logo text book. It was reasonably easy to implement, but although recursive routines are elegant and mentally stimulating, I’ve found that if I don’t work with recursive routines all the time, if I don’t use recursion for everything, then my brain sort of ‘swaps out’ my ability to picture exactly what’s happening when the recursion is going on. Since I like to understand exactly what’s happening in my code, I usually avoid recursion even though it’s beautiful. Also, many modern programming and scripting environments aren’t optimized for things like tail recursion or the giant stacks recursion creates. Blunt, simple iterative routines are easier for me to casually maintain and move from environment to environment.

So, of course, I almost always use simple Bubble sort routines.

Today’s very fast processors make the generally slow routines appear to be quick. The algorithm is simple and it’s easy to implement in almost any environment.

I write a lot of small programs on a Texas Instruments TI-92. (Now it’s called the TI Voyager.) Software on my version includes sort routines that work as standalone procedures but not as generic functions. I’ve coded a simple Bubble sort function that works generically with lists. I don’t like flags, so I actually have two, a routine to sort up — SU(aList) — and a routine to sort
down — SD(aList).

This is the sort up routine. (Sort down, of course, just swaps the greater-than symbol for a less-than symbol in the comparison line.)

Function SU (aList)

Func

Local c, i, j, x

Dim(aList) -> c

For i, 1, c-1
  For j, i+1,c
    If aList[i] > aList[j] Then
      aList[j] -> x
      aList[i] -> aList[j]
      x -> aList[i]
    EndIf
  EndFor
EndFor

Return aList

EndFunc