title: Humanized or natural number sorting of mixed word-and-number strings
body: <p>Following up on <a href="https://stackoverflow.com/q/12916212/398670">this question</a> by <a href="https://stackoverflow.com/users/1176139/sivaram-chintalapudi">Sivaram Chintalapudi</a>, I'm interested in whether it's practical in PostgreSQL to do <a href="http://www.codinghorror.com/blog/2007/12/sorting-for-humans-natural-sort-order.html" rel="noreferrer">natural - or "humanized" - sorting</a> " of strings that contain a mixture of multi-digit numbers and words/letters. There is no fixed pattern of words and numbers in the strings, and there may be more than one multi-digit number in a string.</p>
  
  <p>The only place I've seen this done routinely is in the Mac OS's Finder, which sorts filenames containing mixed numbers and words naturally, placing "20" after "3", not before it.</p>
  
  <p>The collation order desired would be produced by an algorithm that split each string into blocks at letter-number boundaries, then ordered each part, treating letter-blocks with normal collation and number-blocks as integers for collation purposes. So:</p>
  
  <p><code>'AAA2fred'</code> would become <code>('AAA',2,'fred')</code> and <code>'AAA10bob'</code> would become <code>('AAA',10,'bob')</code>. These can then be sorted as desired:</p>
  
  <pre><code>regress=# WITH dat AS ( VALUES ('AAA',2,'fred'), ('AAA',10,'bob') )
  regress-# SELECT dat FROM dat ORDER BY dat;
       dat      
  --------------
   (AAA,2,fred)
   (AAA,10,bob)
  (2 rows)
  </code></pre>
  
  <p>as compared to the usual string collation ordering:</p>
  
  <pre><code>regress=# WITH dat AS ( VALUES ('AAA2fred'), ('AAA10bob') )
  regress-# SELECT dat FROM dat ORDER BY dat;
      dat     
  ------------
   (AAA10bob)
   (AAA2fred)
  (2 rows)
  </code></pre>
  
  <p>However, the record comparison approach doesn't generalize because Pg won't compare ROW(..) constructs or records of unequal numbers of entries.</p>
  
  <p>Given the sample data <a href="http://sqlfiddle.com/#!12/c1700/1" rel="noreferrer">in this SQLFiddle</a> the default en_AU.UTF-8 collation produces the ordering:</p>
  
  <pre><code>1A, 10A, 2A, AAA10B, AAA11B, AAA1BB, AAA20B, AAA21B, X10C10, X10C2, X1C1, X1C10, X1C3, X1C30, X1C4, X2C1
  </code></pre>
  
  <p>but I want:</p>
  
  <pre><code>1A, 2A, 10A, AAA1BB, AAA10B, AAA11B, AAA20B, AAA21B, X1C1, X1C3, X1C4, X1C10, X1C30, X2C1, X10C10, X10C2
  </code></pre>
  
  <p>I'm working with PostgreSQL 9.1 at the moment, but 9.2-only suggestions would be fine. I'm interested in advice on how to achieve an efficient string-splitting method, and how to then compare the resulting split data in the alternating string-then-number collation described. Or, of course, on entirely different and better approaches that don't require splitting strings.</p>
  
  <p>PostgreSQL doesn't seem to support comparator functions, otherwise this could be done fairly easily with a recursive comparator and something like <code>ORDER USING comparator_fn</code> and a <code>comparator(text,text)</code> function. Alas, that syntax is imaginary.</p>
  
  <p><strong>Update:</strong> <a href="http://blog.ringerc.id.au/2012/10/natural-sorting-example-of-utility-of.html" rel="noreferrer">Blog post on the topic</a>.</p>