# Lexicographic ordering of lists-of-lists?

I was surprised to discover that Mathematica does not sort lists-of-lists (LLs) lexicographically by default. For example, applying Sort to {{1, 2}, {3}}, which is already lexicographically ordered, destroys this order, producing {{3}, {1, 2}}.

Is there a standard Mathematica function, or idiom, for lexicographically ordering a LL?

EDIT: If I were to roll my own, I'd implement a lexicographic comparator function, to be passed as the second argument to Sort:

cmpLLs[_][{}, b_List] := True;
cmpLLs[_][a_List, {}] := False;
cmpLLs[by_][a_List, b_List] :=
Module[{va = by[First[a]], vb = by[First[b]]},
If[va == vb, cmpLLs[Rest[a], Rest[b]], va < vb]
];
cmpLLs[a_List, b_List] := cmpLLs[Identity][a, b];

(* test borrowed from Leonid Shifrin's answer *)
test = {{3}, {7}, {4, 6, 2}, {7, 7, 6}, {10, 3, 9}, {6, 7, 9}, {1, 7, 7}};

Sort[test, cmpLLs]
(* {{1, 7, 7}, {3}, {4, 6, 2}, {6, 7, 9}, {7}, {7, 7, 6}, {10, 3, 9}} *)

Sort[test, cmpLLs[Plus]]  (* just for giggles *)
(* {{1, 7, 7}, {3}, {4, 6, 2}, {6, 7, 9}, {7}, {7, 7, 6}, {10, 3, 9}} *)

Sort[test, cmpLLs[Minus]]
(* {{10, 3, 9}, {7}, {7, 7, 6}, {6, 7, 9}, {4, 6, 2}, {3}, {1, 7, 7}} *)


Not a stack-friendly implementation, I admit...

• You could resort to ToString before ordering: ToExpression /@ Sort[ToString /@ {{3}, {1, 2}}] (or roll your own ordering function). Jun 10, 2015 at 13:39
• This is due to Sort on lists sorting by the size of the sub-list first, and only applying lexicographic sort for equal-size lists. This is in fact documented. Jun 10, 2015 at 16:18
• Glad I could help. Re: docs - have a look at the notes in documentation of Sort, under details, fourth bullet point: " usually orders expressions by putting shorter ones first, and then comparing parts in a depth-first manner. ". Jun 10, 2015 at 16:56
• @BlacKow The problem with kjo's implementation is that Mathematica Lists are arrays, not linked lists. So, apart from the issues related to tail calls, there is also the issue related to list copying on every recursive step. The proper way to do this sort of things in Mathematica would be to use linked lists. Jun 11, 2015 at 2:15
• The reason to sort on length first is that it is often a quick discriminator, hence Ordering is less likely to be slow e.g. from deep recursion in a depth first search. Jun 11, 2015 at 20:56

This is due to Sort on lists sorting by the size of the sub-list first, and only applying lexicographic sort for equal-size lists. This is in fact documented.

Based on this observation, here is one possibility:

ClearAll[lexicographicListSort]
lexicographicListSort[lst_List] :=
Module[{lengths = Length /@ lst, ord},
ord = Ordering @ PadRight[lst, {Length[lst], Max[lengths]}];
]


For example:

test = {{3}, {7}, {4, 6, 2}, {7, 7, 6}, {10, 3, 9}, {6, 7, 9}, {1, 7, 7}}

lexicographicListSort[test]

(* {{1, 7, 7}, {3}, {4, 6, 2}, {6, 7, 9}, {7}, {7, 7, 6}, {10, 3, 9}} *)


EDIT

As BlacKow rightly noted, the above code can be very memory-inefficient, in cases when some of the sublists are really large. The simplest naive solution to trade speed for memory is to make such padding local to the comparison event:

sortlNaive[l_List] :=
Sort[
l,
With[{max = Max[Length[#1], Length[#2]]},
] &
]


However, this method is pretty inefficient. The reason is that we are leaving the "optimal code" Mathematica's paradigm to work with lots of data at once (it is possible to explain this particular case in more detail).

Saving explanations and benchmarks for some near future (when I get more time), here is a version which generally performs better or much better than sortlNaive, while being much more memory-efficient than lexicographicListSort (V10+, since I use operator forms, but can be easily rewritten to be used in earlier versions):

ClearAll[sortl];
sortl[{}, _ : None] := {};
sortl[{x_}, _ : None] := {x};
sortl[l_List] := sortl[l, 1];
sortl[l_List, lev_] :=
With[{min = Min[Length /@ l]},
Composition[
Flatten[#, 1] &,
Map[
If[Length[#] == 1,
#,
With[{smallest = LengthWhile[#, Length[#] == lev &]},
Take[#, smallest]~Join~sortl[Drop[#, smallest], lev + 1]
]
] &
],
SplitBy[#, Take[#, {lev, min}] &] &,
SortBy[Take[#, {lev, min}] &]
]@l
]


A question of automation of the choice between lexicographicListSort and sortl is an interesting one, but requires more time than I currently have, to do it justice.

• What if the average length of your sub-list is 5, but the largest sub-list has million elements? Your padding will be wasting lots of memory, right? Jun 10, 2015 at 17:20
• @BlacKow Yes, you are right, that's a good point! I added some code to address that issue. Jun 11, 2015 at 1:49