Golfed sort by debian version number
Ruby 2.0, 145 179 characters

puts$&lt;.sort_by{|a|(1..3).map{|i|"#{a[/^(\d+:)?(.+?)(-[^-]+)?
/,i]}".scan(/(\D*)(\d*)/).map{|w,n|w.bytes.map{|c|c&lt;126?c&gt;58?c:c+99:-1}+[0,n.hex]}}}


Correctly sorts both the linked reference input (though it generates a slightly different output order due to different sorting of equivalent version numbers, e.g. 1.06-2 vs 1.6-2) and the included test data.