Ordering problem

Question

Let's look at the following example.

Ordering[{0, 20 Sqrt[5], 40 Sqrt[5], 20 Sqrt[5], 20 Sqrt[10]} // N]

gives the right answer

{1, 2, 4, 5, 3}

but if one removes the N, one gets the wrong answer

Ordering[{0, 20 Sqrt[5], 40 Sqrt[5], 20 Sqrt[5], 20 Sqrt[10]}]

{1, 2, 4, 3, 5}

Is it a bug?

Answer 1

This is probably because by default Sort doesn't just use numerical values, it includes structure information as well. From the doc:

Numeric expressions are sorted by structure as well as numerical value:

In[1]:= Sort[{Sqrt[2], 1, 2, 1/Sqrt[2]}]

Out[1]= {1, 2, 1/Sqrt[2], Sqrt[2]}

Sort by numerical value only:

In[2]:= Sort[{Sqrt[2], 1, 2, 1/Sqrt[2]}, Less]

Out[2]= {1/Sqrt[2], 1, Sqrt[2], 2}

along with the following doc:

Sort usually orders expressions by putting shorter ones first, and then comparing parts in a depth-first manner.

gives us a hint why. If you run TreeForm /@ {0, 20 Sqrt[5], 40 Sqrt[5], 20 Sqrt[5], 20 Sqrt[10]}, you'll see that the last layer (Rational) is the same for all four Sqrts. Then the next depth down is the Power, in which 10 is the outlier, and is greater than 5, so will be placed last. Finally, comparing {20, 40, 20} will give the ordering {1, 3, 2}, which when put together with the original list gives you the ordering:

In[77]:= Ordering[{0, 20 Sqrt[5], 40 Sqrt[5], 20 Sqrt[5], 20 Sqrt[10]}]

Out[77]= {1, 2, 4, 3, 5}

Answer 2

No, this is not a bug, and Ordering does not give a wrong answer.

Quoting the documentation of Sort,

Sort[list,p] applies the function p to pairs of elements in list to determine whether they are in order. The default function p is OrderedQ[{#1, #2}] &.

As you can see, Sort (and Ordering) compares using OrderedQ, not Less.

OrderedQ uses a special ordering that is applicable to any Mathematica expressions, not just numbers. Read about it on the doc page of Sort.

The rule I believe applies here is the following:

Sort treats powers and products specially, ordering them to correspond to terms in a polynomial.

This means that terms are interpreted as if they were in the form 10 var1 + 20 var2, i.e. variables with coefficients. The ordering is determined by the ordering of "variables" (which in your example correspond to Sqrt[5] and Sqrt[10]), and not their coefficients. Thus the canonical ordering is {40 Sqrt[5], 20 Sqrt[20]} and not the reverse, because Sqrt[5] comes before Sqrt[10] in the canonical order.

The reason for doing this is that Orderless functions will auto-sort their arguments in the same way. Thus if you write a polynomial, 10 y + 20 x, it'll be ordered on the variables yielding 20 x + 10 y.

---

So, if you want numerical expressions sorted by numerical magnitude, use

SortBy[list, N]

If you want to get the permutation that sorts them, use

Ordering[ N[list] ]

Answer 3

NumericalSort

This behavior of Sort is indeed the documented behavior. However I also find it not intuitive.

There is a function called NumericalSort (as of Mathematica 11.1) which sorts the elements of a list by numerical order. It uses NumericalOrder as the ordering function i.e. Sort[list, NumericalOrder].

Examples

(* different results *)

         Sort[{1, -Pi}] -> {1, -Pi}
NumericalSort[{1, -Pi}] -> {-Pi, 1}

         Sort[{{1, 2}, {-Pi, 2}}] -> {{1, 2}, {-Pi, 2}}
NumericalSort[{{1, 2}, {-Pi, 2}}] -> {{-Pi, 2}, {1, 2}}


         Sort[{{"b", 2}, {Pi, 1}}] -> {{"b", 2}, {Pi, 1}}
NumericalSort[{{"b", 2}, {Pi, 1}}] -> {{Pi, 1}, {"b", 2}}


(* same results *)

         Sort[{{"b", 2}, {"a", 1}}] -> {{"a", 1}, {"b", 2}}
NumericalSort[{{"b", 2}, {"a", 1}}] -> {{"a", 1}, {"b", 2}}