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 self-explanatory. We use several built-in 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 pattern-matcher, 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:

Global`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 pattern-matcher 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.

For us it is obvious that the pattern {sorted_List,{}} represents a specific case of {sorted_List, unsorted_List}. But not so for Mathematica! This kind of situations often result in some quite subtle bugs in the programs that use functions with multiple definitions.   Of course, we may blame the system, but it will be more useful to understand why this happened. The point is that the way Mathematica's pattern-matcher determines which rule is more specific, is completely syntax-based, rather than semantics-based. The pattern {} is syntactically different from <unsorted_List>, and determining that one is a special case of the other is already a semantic operation. Here is what we had to add instead, had we wished Mathematica to understand it:  
iterSort[{sorted_List,unsorted_List}]/;unsorted==={}:={sorted,{}}.

Let us check:

Check now:

Global`iterSort

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:

Created by Wolfram Mathematica 6.0  (05 February 2009)