Lexicographic ordering of lists-of-lists?

Question

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...

Answer 1

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]}];
    MapThread[Take, {lst[[ord]], lengths[[ord]]}]
  ]

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]]}, 
      OrderedQ[PadRight[#, max] & /@ {##}]
    ] &
  ]

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.