まずは与えられる文字列の先頭に0 がつかない場合の問題を考えてみましょう。

この場合は、単に与えられた文字列を数としてソートすればよいです。しかし、C++,Javaなどでは、整数型は \(20\) 桁程度まで、浮動小数点数型も \(300\) 桁程度までの数しか扱うことができないため、問題で入力されうる最大 \(100000\) 桁の数に対応することはできません。多倍長整数型を使うのも手段の1つですが、次のようにすることで、文字列のまま大小関係を比較することができます。

1. もし桁数(=文字列長)が異なるなら、桁数の小さい方が小さい
2. 桁数が等しいなら、文字列として辞書順で小さい方が小さい

このような比較関数を用いてクイックソートなどを行うことで、与えられた文字列長の合計を \(S\) として \(O(S\log S)\) の時間でソートすることができます。

先頭に 0 がつくものがある場合も同様で、予め先頭の 0 の個数をカウントして取り除いておくことで

1. 先頭の 0 を取り除いた桁数を比較
2. 先頭の 0 を取り除いた文字列を比較
3. 先頭の 0 の個数を比較

として同様に \(O(S\log S)\) の時間でソートすることができます。