Sorting number strings numerically
Fun problem, at least abstractly. Here&#x27;s a similar, maybe more basic approach for positive integers. It uses the idea at the beginning of the article to store numbers in unary, to store the length of the number in unary ... recursively. The idea is to sort by ... the length of the length of the length of the number, then by the length of the length of the number, then by the length of the number, then by the number.<p>First, imagine we store the number in the form<p><pre><code>    aaaaaaaaaaa 92389210184
</code></pre>
where the number of a&#x27;s is equal to the length of the number. This encoding scheme works for the same reasons as discussed in the article. And it only takes 2*(length of original number)+1 characters.<p>But now, we can do better by applying the same encoding scheme to the &#x27;aaaaaaaaaaa&#x27;. That is, suppose the original number is 295 digits long. The number 295 is 3 digits long. So we store the number with 3 b&#x27;s, as:<p><pre><code>    bbb 295 109382388575782352353453....
</code></pre>
OK, but what if we want to store a number that&#x27;s 4,000,000,000 digits long? This would look like<p><pre><code>    bbbbbbbbbb 4000000000 109382388575782352353453....
</code></pre>
And that&#x27;s a bit wasteful. If there are more than two b&#x27;s, then we can recursively apply the encoding to the b&#x27;s. There are 10 b&#x27;s, and 10 has two digits, so we get<p><pre><code>    cc 10 4000000000 109382388575782352353453....
</code></pre>
And so on. (We won&#x27;t ever have hard drives that can make use of letters e and above, so it can probably stop there.)<p>So the encoding schemes look like<p><pre><code>    a n                            # n is only one digit
    aa n                           # n is two digits
    b log10(n) n                   # log10(n) is one digit
    bb log10(n) n                  # log10(n) is two digits
    c log10(log10(n)) log10(n) n   # log10(log10(n)) is one digit
    cc log10(log10(n)) log10(n) n  # log10(log10(n)) is two digits
    d log10(log10(log10(n))) log10(log10(n)) log10(n) n
    ...</code></pre>