Is there a "precedence table" for the canonical Sort ordering?

Question

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.

Answer 1

So I think the docs are mostly clear, if hard to visualize. Here's my version of such a table:

{
     "Numerics" ->
      {
       "Negative Integer" -> -1,
       "Zero" -> 0,
       "Positive Integer" -> 1,
       "Negative Float" -> N@-\[Pi],
       "Positive Float" -> N@\[Pi],
       "Symbolic Constant (Pi)" -> \[Pi],
       "Symbolic Constant (E)" -> E,
       "Imaginary (Zero Real Part)" -> I,
       "Imaginary (Positive Real Part)" -> 1 + I,
       "Imaginary (Negative Real Part)" -> -1 + I,
       "Root" -> Sqrt[a],
       "Cube Root" -> CubeRoot[a],
       "Power" -> Power[a, 5],
       "Subtract" -> a - b,
       "Add" -> a + b,
       "Divide" -> a/b,
       "Multiply" -> a*b
       },
     "Strings" ->
      {
       "Plus" -> "+",
       "Minus" -> "-",
       "Equals" -> "=",
       "Divide" -> "\[Divide]",
       "Slash" -> "/",
       "Question" -> "?",
       "Paren Left" -> "(",
       "Paren Right" -> ")",
       "Bracket Left" -> "[",
       "Bracket Right" -> "]",
       "Angle Left" -> "<",
       "Angle Right" -> ">",
       "Curly Left" -> "{",
       "Curly Right" -> "}",
       "Association Left" -> "\[LeftAssociation]",
       "Association Right" -> "\[RightAssociation]",
       "Number Char" -> "1",
       "Lowercase ASCII Char" -> "a",
       "Uppercase ASCII Char" -> "A",
       "Lowercase Non-ASCII Char" -> "ü",
       "Uppercase Non-ASCII Char" -> "Ü",
       "Lowercase ASCII Word" -> "gunther",
       "Uppercase ASCII Word" -> "Gunther",
       "Lowercase Non-ASCII Word" -> "günther",
       "Uppercase Non-ASCII Word" -> "Günther",
       "Lowercase Script Char" -> "\[ScriptA]",
       "Lowercase Greek Char" -> "\[Alpha]",
       "Lowercase Gothic Char" -> "\[GothicA]",
       "Hebrew Char" -> "\[Aleph]"
       }
     } //
    Append[#,
      With[{
        e = Expr[],
        sa1 = SparseArray[{1, 2, 3}],
        sa2 = SparseArray[{"a", "b", "c"}],
        sa3 = SparseArray[Band[{1, 1}] -> {1, 2, 3, 1}],
        sa4 = SparseArray[Band[{2, 2}] -> {1, 2, 3}]
        },
       System`Private`SetNoEntry[e];
       "Expressions" ->
        {
         "Symbol" -> a,
         "Basic" -> expr[],
         "Call" -> expr @@ Map[Last@*First@*Last]@#,
         "List" -> Map[Last@*First@*Last]@#,
         "Association" -> Association@Map[First@*Last]@#,
         "Association 1" -> <|"Association" -> 1, "b" -> -100|>,
         "Association 2" -> <|"Sorts" -> 1, "b" -> -100|>,
         "Association 3" -> <|"By" -> 1, "b" -> -100|>,
         "Association 4" -> <|"Key" -> 1, "b" -> -100|>,
         "Association 5" -> <|-100 -> 1, "b" -> -100|>,
         "SparseArray 1" -> sa1,
         "SparseArray 2" -> sa2,
         "SparseArray 3" -> sa3,
         "Sparse Array 4" -> sa4,
         "SparseNotArray" -> SparseNotArray[{1, 2, 3}],
         "NoEntryExpr" -> e
         }
       ]
      ] & // 
   Map[ReplaceAll[Rule[k_, k2_ -> v_] :> {k, k2, v}]@*Thread] // 
  Apply[Join] /* SortBy[Last] //
 Grid[List @@@ #,
   Dividers -> GrayLevel[.8],
   Background -> {{GrayLevel[.95], GrayLevel[.95], None}, None},
   Alignment -> Left
   ] &

(had to chop the table in two to upload it via Imgur)

Note that the basic numerics and strings are pretty clear from the docs. The only real oddities come from the expressions.

One case not treated in the docs is Association which of course has some structural quirks do it. Clearly it's sorting is by key, not value, and it sorts between numerics and strings.

Another oddity is CubeRoot. I have no idea what's up with that. Maybe such a table should exist so WRI would catch corner-case bugs (I think that's a bug) like that.

Note that SparseArray sorts like its content, which is vaguely surprising given how that content is stored, even if that content isn't specified. Whether or not this has performance implications isn't something I've tested.

Another thing tested is that System`Private`NoEntryQ expressions don't sort oddly, either, except for Association.

Answer 2

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.

Answer 3

After a few minutes of extreme confusion, I have discovered that Sort puts all integers and rational numbers before all expressions involving square roots, which in turn go before predefined constants like $e$ and $\pi$:

OrderedQ[N[{-Sqrt[2], -1, 0, 1/2, 1, Sqrt[2], E, \[Pi], Sqrt[15]}]]
>> True

Sort[{-Sqrt[2], -1, 0, 1/2, 1, Sqrt[2], E, \[Pi], Sqrt[15]}]
>> {-1, 0, 1/2, 1, -Sqrt[2], Sqrt[2], Sqrt[15], E, \[Pi]}