# Is there a “precedence table” for the canonical Sort ordering?

This answer in which I wrote about the Operator Precedence Table was unexpectedly popular.
That got me thinking about similar things, and I am wondering:

Does an "ordering table" exist for the canonical order used by Sort and similar functions?
(Ordering, Order, OrderedQ)

It's easy enough to test the ordering of various expressions, but just as the precedence table contains some surprises even for experienced users I'm wondering if the canonical ordering does too? It seems odd if this isn't spelled out clearly somewhere, yet I don't recall seeing such a list.

The documentation for Order tantalizingly says:

Order uses canonical order as described in the notes for Sort.

Yet the documentation for Sort is quite basic, as far as I can find, saying only:

• Sort by default orders integers, rational, and approximate real numbers by their numerical values.
• Sort orders complex numbers by their real parts, and in the event of a tie, by the absolute values of their imaginary parts.
• Sort orders symbols by their names, and in the event of a tie, by their contexts.
• Sort usually orders expressions by putting shorter ones first, and then comparing parts in a depth-first manner.
• Sort treats powers and products specially, ordering them to correspond to terms in a polynomial.
• Sort orders strings as in a dictionary, with uppercase versions of letters coming after lowercase ones. Sort places ordinary letters first, followed in order by script, Gothic, double-struck, Greek, and Hebrew. Mathematical operators appear in order of decreasing precedence.

This describes how Sort treats certain classes of expressions but it doesn't describe the relative ordering of these classes or attempt in any way to be exhaustive.

-
One consequence of canonical ordering is that e.g. symbols and strings are not sorted intuitively. In canonical ordering the order is {a1, a10, a2, a9} while intuitive sorting gives {a1, a2, a9, a10}. This comes handy when sorting files for example. –  István Zachar Aug 28 '13 at 12:56
Furthermore, the last point is either confusing or downright wrong: Sort@{"a", "A", "á", "Á"} yields {"a", "á", "A", "Á"}, which seems to imply that Mathematica cannot really distinguish accented characters (as it was already discussed here). –  István Zachar Aug 28 '13 at 12:58
@IstvánZachar yes the first point is a typical computation problem - the intuitive sorting - more well known as natural ordering has to be done in another manner (see mathematica.stackexchange.com/questions/10619/…). That last point on accented character is indeed quite a surprise! –  Jonie Aug 28 '13 at 14:03

Ahh good fun questions. Anyway this isn't a comprehensive answer but rather just a quick test on the basics:

list = {0.1, I, 2 + I, 0, 2 , 2 x, x, xxx, 2^x, x^2, x^x, x^ (2 x), X, xX, "y", "yy", "Y"};
Sort[list]


{0, I, 0.1, 2, 2 + I, 2^x, "y", "Y", "yy", x, 2 x, x^2, x^x, x^( 2 x), X, xX, xxx}

Only thing that grabs my attention is imaginary numbers - with the imaginary part counting as a value greater than zero but less than any positive number. Other than that, seems like numeric values first, followed by strings, then symbols. Each section is ordered according the documentation of Sort that was mentioned in the post.

-
Sort@Transpose@{list, Ordering@Ordering@list} => {{0, 1}, {I, 2}, {0.1, 3}, {2, 4}, {2 + I, 5}, {2^x, 6}, {"y", 7}, {"Y", 8}, {"yy", 9}, {x, 10}, {2 x, 11}, {x^2, 12}, {x^x, 13}, {x^(2 x), 14}, {X, 15}, {xX, 16}, {xxx, 17}} and, as far as I know, the following (always?) holds: (Sort@mylist)[[Ordering@Ordering@mylist]] == mylist (see here). [+1,btw] –  TomD Aug 28 '13 at 15:37