30
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – István Zachar Aug 28 '13 at 12:56
  • 2
    $\begingroup$ 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). $\endgroup$ – István Zachar Aug 28 '13 at 12:58
  • $\begingroup$ @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! $\endgroup$ – Jonie Aug 28 '13 at 14:03
16
+50
$\begingroup$

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)

table pt 1

table pt 2

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.

$\endgroup$
  • $\begingroup$ +1 for the first attempt in this Q&A to create a table. Thank you. $\endgroup$ – Mr.Wizard Aug 3 '17 at 16:17
  • $\begingroup$ @Mr.Wizard unfortunately I've already realized it's lacking. I'm guessing something like SparseArray and other "NoEntry" type constructs sort oddly, perhaps even more so than Association. After I read that "Inside the Pattern Matcher" notebook I'll look at that and update. $\endgroup$ – b3m2a1 Aug 3 '17 at 16:28
  • $\begingroup$ I didn't imagine it to be exhaustive, but I sincerely appreciate the effort and I look forward to your update. :-) $\endgroup$ – Mr.Wizard Aug 3 '17 at 16:33
  • $\begingroup$ @Mr.Wizard just checked some basic NoEntry types. They seem to sort normally, which is nice. Not as many surprises hiding here as I expected. $\endgroup$ – b3m2a1 Aug 3 '17 at 19:09
  • 1
    $\begingroup$ CubeRoot evaluates to Surd, and Surd is the actual oddity. If you do Sort[Unevaluated@{...}] with CubeRoot inside, you'll notice CubeRoot is ranked somewhere closer to 'expressions'. $\endgroup$ – QuantumDot Jul 9 '18 at 16:15
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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] $\endgroup$ – user1066 Aug 28 '13 at 15:37
5
$\begingroup$

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]}
$\endgroup$
  • 6
    $\begingroup$ This happens to be a known issue, but it is this kind of issue that inspired my question, and I am discouraged that four years later we still don't have an answer. This should be foundational information about ordering in Mathematica, not guesswork. See (2729) and its linked questions. $\endgroup$ – Mr.Wizard Aug 1 '17 at 9:51
  • $\begingroup$ The constants are really just symbols with something like NValues on them, so they do accord with the provided spec in the Sort docs. $\endgroup$ – b3m2a1 Aug 1 '17 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.