
5.4.1.7 Case study: Sorting a list of numbers The problem Let us start with a list of numbers:
We would like now to sort this list in the decreasing order according to the following algorithm: at any given time, we maintain a list with two sublists: the first (initially empty) gives the numbers that are already sorted, the second (initially coinciding with the original list) contains the numbers not yet sorted. A single iteration consists of finding a maximal number in the unsorted part, deleting it from there and appending it to the list of sorted numbers. The number of iterations needed to sort a list is obviously equal to the length of the list. The sketch of the solution Here is a function which realizes a single iteration:
The code is more or less selfexplanatory. We use several builtin functions, such as Max, Position, Append, Delete. Let us use it now on our test list. This is how it looks at some intermediate sorting step:
To sort the list completely:
Possible bugs and automatic rule reordering It is amusing to see what happens if we by mistake use one (or more) extra iteration
This is due to the following behavior (or convention):
If we want to be on the safe side, we will add one more definition to our function <iterSort>:
This last definition is supposed to return back the list unchanged, once the <unsorted> part is empty. Also, because it is more specific than the first, we expect Mathematica to attempt to use it before it attempts to use the more general one (this is a standard rule of Mathematica patternmatcher, see sections 1.2.8, 4.7.2, 4.7.3). Well, in this case we expect too much. Let us test the new function:
It does not seem to work. To see what happens, let us look at the new definition of iterSort:
We now see the reason: the newly added rule is placed after the main definition, and thus, has no chance to apply. But this behavior contradicts our expectations! As we know (section 1.2.8), the more specific rules are always placed by the Mathematica patternmatcher before the more general ones, when it can determine it. By more specific I mean the rule whose pattern is completely contained in another (more general) rule's pattern as a special case.
Check now:
We see that the rules have been interchanged. Of course, on the practical side, to be completely sure one can just enter the rules in the right order from the very beginning, but it is important to also understand what is going on behind the scenes. Let us check our final variant now:
Now everything works. Use NestList to see intermediate steps The existence of the NestList command allows us to see all of the intermediate steps of our sorting algorithm without any extra cost  just change Nest to NestList:
This capability is often quite handy, in particular for debugging programs which use Nest. Final solution Finally, let us package our entire sort procedure into a function: first, here is our <iterSort> function once again:
Now, the sorting function:
Test:

