How do you "sordid sort" alphanumeric strings? The question is about sorting alphanumeric string in a "more natural" order. Source: Marc LeBrun's "Sordid Sort" Computist Quiz


  Often a system string comparison sorts alphanumeric data “unnaturally”, as with these filenames:

File1
File10 ← ?
File11 ← ?
File12 ← ?
File2
File3
File3X
File4
File5
File6
File7
File8
File999

  
  Describe an algorithm that will sort alphanumeric strings in a “more natural” order:

File1
File2
File3
File3X
File4
File5
File6
File7
File8
File10
File11
File12
File999

  
  The algorithm may only rely on comparing characters; to avoid overflow problems with very long numbers it must not convert substrings of digits into their numerical values.


Spoiler alert: If you would like to independently solve the above, please do so now before you let the below spoil it for you.

This implementation has its inspiration from Computist Quiz Answer Guide. Misunderstandings would be mine.

From the Answer Guide: Extra credit: discuss the behavior with respect to leading zeros, as in “007”.

#!/usr/bin/perl -w

# Sordid Sort: http://fxpt.com/wp-content/uploads/2012/01/quiz.pdf
# Solution based on http://fxpt.com/wp-content/uploads/2012/01/QuizAnswers.pdf

use strict;

my $verbose = 0;    # set it to non-zero to get regex matches printed to STDERR
my $ALNUM = qr/(\D*)(\d*)/; # match a pair of alphas-optional and/or num-optional
my @in = ();

while (&lt;&gt;) {
    chomp;
    push @in, $_; 
}

sub sordidcmp {
    my @a = $a =~ m/$ALNUM/g;   # always even number of elements since $ALNUM matches in pairs; and always has a sentinel pair
    my @b = $b =~ m/$ALNUM/g;
    my $cmp = 0;
    my $min_ab = (@a &lt; @b) ? @a : @b;
    my $i;
    print STDERR "comparing (&lt;".join("&gt; &lt;", @a)."&gt;) with (&lt;".join("&gt; &lt;", @b)."&gt;)" if $verbose;
    for ($i = 0; $i &lt; $min_ab; ++$i) {  # advance by 2; once here
        $cmp = $a[$i] cmp $b[$i];   # compare alphas
        last if $cmp;    # end if we found unequals

        ++$i;       # advance once more here
        # compare nums
        my $lenai = length($a[$i]);
        my $lenbi = length($b[$i]);

        # deal with Extra credit: prefix "0" to the shorter num
        if ($lenai &lt; $lenbi) {
            $a[$i] = ("0" x ($lenbi-$lenai)).$a[$i];
        } elsif ($lenbi &lt; $lenai) {
            $b[$i] = ("0" x ($lenai-$lenbi)).$b[$i];
        }

        $cmp = $a[$i] cmp $b[$i]; # note: stringwise compare of nums
        last if $cmp;    # end if we found unequals
    }
    print STDERR " = $cmp\n" if $verbose;
    return $cmp;
}

print join "\n", sort sordidcmp @in;
print "\n" if @in;  # guard against empty input


My questions are:


I observed that the match @a = $a =~ m/$ALNUM/g always produces a sentinel pair of ("", ""). Is the above code relying on undocumented behaviour? I could not find (read: understand) this from the perlop, perlretut, and perlre perldocs.
Can you help simplify the sordidcmp subroutine? Perl golf would be nice, but a more maintainable version is what I would be interested in. Of course, links to other solutions/implementations are welcome.
I observed that the match @a = $a =~ m/$ALNUM/g always produces a sentinel pair. Is the above code relying on undocumented behaviour?


I don't know what you mean by "sentinel pair", but that will always return two values per match since you have two captures.


  Can you help simplify the sordidcmp subroutine?


You could replace sort sordidcmp with Sort::Key::Natural's natsort.