Tab Completion

I'm Tab Atkins Jr, and I wear many hats. I work for Google on the Chrome browser as a Web Standards Hacker. I'm also a member of the CSS Working Group, and am either a member or contributor to several other working groups in the W3C. You can contact me here.
Listing of All Posts

Creating ASCII-Sortable Strings from Numbers

Last updated:

How many times have you had to create a bunch of numbered files or whatever, and you want them to sort in proper numerical order? If you don't have a smart sorter that can detect numbers, you probably used zero-padding to make the numbers the same length, so they'll sort properly as strings.

That method has some annoying drawbacks. It requires you to know ahead of time how large of numbers you'll see, and it adds a lot of overhead to each string.

Here's a very simple alternate method that's produces properly-sorting strings that are just as easy to read, that works for any number whatsoever without having to plan ahead, and that adds a minimal amount of overhead to each string:

function sortableStringFromNum(num) {
  if(num < 10) return ''+num;
  var str = '-'+num, prefix = '';
  num += '';
  while(num.length > 1) {
    num = '' + num.length;
    prefix += 'A';
    str = num + str;
  }
  return prefix + str;
}

function numFromSortableString(str) {
  return +str.substr(str.indexOf('-')+1);
}

This adds no overhead for numbers 0 to 9, 3 characters of overhead for numbers 10 to 1billion - 1, and 6 characters of overhead for numbers 1billion to 1e99 - 1. In general, the overhead is roughly equal to log(log(number)), which is ridiculously tiny.

Here's a few examples of what it produces:

0 => "0"
9 => "9"
10 => "A2-10"
300 => "A3-300"
1 million => "A7-1000000"
1 billion => "AA210-1000000000"

This method wasn't invented by me - it was created in a thread on the XKCD forums named Generating savegame names so they appear in sorted order, where we did our usual over-thinking thing and competed to produce the best method that would work on arbitrarily-large numbers.

(a limited set of Markdown is supported)