Sort all levels of expression

Question

What's a good way to Sort all levels of an expression? The following does what I want when expression has rectangular structure, but I'd like it to work for non-rectangular expressions as well

Map[Sort, {expr}, Depth[expr] - 1]

For instance, the following should print True

sorted = deepSort[{{{1, 3, 8}, {3, 7, 6}, {10, 4, 9}, {3, 8, 10, 
      6}, {8, 2, 5, 10}, {8, 5, 10, 
      9}}, {{{1, 3, 8}, {3, 8, 10, 6}}, {{3, 7, 6}, {3, 8, 10, 
       6}}, {{10, 4, 9}, {8, 5, 10, 9}}, {{3, 8, 10, 6}, {8, 2, 5, 
       10}}, {{8, 2, 5, 10}, {8, 5, 10, 9}}}}];
checkSortedLevel[k_] := Map[OrderedQ, sorted, {k}];
And @@ Flatten[checkSortedLevel /@ Range[0, 2]]

Answer 1

deepSort[expr_] := Map[Sort, expr, {0, -2}]

Note that this will work even if your expr contains heads other than List.

Answer 2

Should you have an expression that contains heads other than List, and you do not want to sort those, this may be useful.

expr /. List :> Composition[Sort, List]