# Can the elements of a list always be sorted into a canonical order?

As the title states - does a unique order exist for any Mathematica list to be sorted by the Sort[] function (or as returned by a function that treats lists as sets)?

While I'm pretty sure the answer is yes, the kinds of elements you can throw into a Mathematica list seems so general and varied (numbers, strings, symbols, images, graphs, other lists, etc., etc.) that I thought to make sure.

(The reason this question occurred to me is an exercise question asked in the book I just started learning Mathematica from: Write a function SubsetQ[list1, list2] that checks whether list1 is a subset of list2. My solution is

SubsetQ[lis1_, lis2_] := Intersection[lis1, lis2] == Union[lis1, {}]
(* thanks to Simon Woods' correction, and assuming Intersection and Union sort canonically *)


but that implicitly assumes that the two lists on either side of the equality check will be sorted in the same order.)

-
"Write a function SubsetQ[]..." - you've already seen MemberQ[]? – J. M. Apr 3 '13 at 8:17
Yes, I have. What solution would you like to suggest? (If it involves iteration, then that occurred to me, but since the book hasn't gotten to it yet I didn't consider it any further.) – Aky Apr 3 '13 at 8:31
There is a canonical order. See : reference.wolfram.com/legacy/v5_2/book/section-A.3.9 – andre Apr 3 '13 at 8:39
@belisarius I would say since in Mathematica anything can be a list-element, Intersection must deal with general lists, which implies that its sorting function should be one that can sort any expression type. And since canonical sorting is such (and I don't think any other sorting is used generally in Mathematica) I would presume Intersection uses canonical sorting. To prove it would require someone to test all the specifications of the standard order linked by andre above. So in short: no, I don't know how to quickly test Intersection's sorting order :) – István Zachar Apr 3 '13 at 9:16
From my experience, the answer is yes - the default sorting function is the same for Union, Intersection and Complement. As a side note, you could avoid this problem in this particular case by using something like SubsetQ[lis1_, lis2_] := Complement[list1, list2] === {}. – Leonid Shifrin Apr 3 '13 at 10:12

As several others have pointed out, there exists a canonical ordering for any Mathematica expression. Quoting the list:

• Integers, rational and approximate real numbers are ordered by their numerical values.
• Complex numbers are ordered by their real parts, and in the event of a tie, by the absolute values of their imaginary parts.
• Symbols are ordered according to their names, and in the event of a tie, by their contexts.
• Expressions are usually ordered by comparing their parts in a depth-first manner. Shorter expressions come first.
• Powers and products are treated specially, and are ordered to correspond to terms in a polynomial.
• Strings are ordered as they would be in a dictionary, with the upper-case versions of letters coming after lower-case ones. Ordinary letters appear first, followed in order by script, Gothic, double-struck, Greek and Hebrew. Mathematical operators appear in order of decreasing precedence.

In your specific case, you can avoid having to sort anything by just taking the Complement, as Leonid mentioned:

SubsetQ[lis1_, lis2_] := Complement[list1, list2] === {}

-