Skip to content

Sort

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description

Sort[list] sorts the elements of list into canonical order.
Sort[list, p] sorts using the ordering function p.

Examples

All examples below are verified against the current Mathilda build.

In[1]:= Sort[<|"a" -> 3, "b" -> 1, "c" -> 2|>]
Out[1]= <|"b" -> 1, "c" -> 2, "a" -> 3|>

In[2]:= SortBy[<|"a" -> {9}, "b" -> {1}|>, First]
Out[2]= <|"b" -> {1}, "a" -> {9}|>

In[3]:= Total[<|"a" -> 3, "b" -> 1, "c" -> 2|>]
Out[3]= 6

In[4]:= Join[<|"a" -> 1, "b" -> 2|>, <|"b" -> 3, "c" -> 4|>]
Out[4]= <|"a" -> 1, "b" -> 3, "c" -> 4|>

Implementation notes

Algorithm. builtin_sort deep-copies the argument list's elements into an Expr** array and sorts it in place with the C library qsort. With no ordering function it uses expr_compare (the canonical Order); with a second argument p it calls p[a, b], evaluates the result, and treats True/1 as "in order" and False/-1 as "out of order". The custom comparator is passed to qsort through a file-scope current_sort_p pointer (saved/restored around the call so reentrant sorts nest correctly). The original head is preserved, so Sort works on any expression, not just List.

Canonical order (expr_compare). Defined in this file (co-located with Sort/OrderedQ and also used by the evaluator's Orderless argument-sorting): (1) numeric atoms (Integer, Real, Rational, BigInt, MPFR) sort first by value, integers compared exactly via GMP; (2) strings next, case-insensitive then case-sensitive lexicographic; (3) everything else is compared by a polynomial degree vector — collect every symbol name in either operand, sort those names in reverse-alphabetical order (so the lex-last variable is most significant), and lexicographically compare the per-variable degrees (expr_poly_degree, which returns +∞ for non-polynomial occurrences). This gives the grevlex-with-reverse-alpha display order. (4) Ties break structurally: bare symbol before compound, then head, arity, and args recursively.

Complexity. O(n log n) comparisons; each expr_compare is itself O(symbols × tree size) because it rebuilds the symbol set per pair. The comparator is deliberately made symmetric (order-independent symbol collection) so qsort cannot oscillate on Orderless heads with many unknowns.

Attributes: Protected.

Implementation status

Stable — documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

References

Notes & additional examples

Worked examples

In[1]:= Sort[{3, 1, 2}]
Out[1]= {1, 2, 3}

In[2]:= Sort[{5, 3, 8, 1}, Greater]
Out[2]= {8, 5, 3, 1}

In[1]:= Sort[{x^2, x, 1, x^3}]
Out[1]= {1, x, x^2, x^3}

In[2]:= Sort[{"banana", "apple", "cherry"}]
Out[2]= {"apple", "banana", "cherry"}

In[1]:= Sort[{{2, 1}, {1, 3}, {1, 2}}]
Out[1]= {{1, 2}, {1, 3}, {2, 1}}

In[2]:= Sort[Range[10], (Mod[#1, 3] < Mod[#2, 3]) &]
Out[2]= {3, 9, 6, 10, 1, 7, 4, 2, 8, 5}

Notes

Sort[list] orders elements by Mathilda's canonical ordering, which compares numbers numerically, strings lexicographically, and structured expressions component-by-component (so the nested lists sort by first element, then second). Sort[list, p] uses an ordering predicate p[a, b] instead: Greater reverses to descending order, and a pure function such as Mod[#1, 3] < Mod[#2, 3] groups by residue class. The sort is stable, so equal-ranked elements keep their original relative order.