There are lots of links around, many of them linked from the node I linked to, but if you do not understand the explanations there, the others may also leave you cold.

I'll have a go at explaining them, but I doubt I will do much better than others.

Simple sorting using sort

The basic way of sorting in perl is to use the built in sort function.

1. my @sortedAlpha = sort @alphaData;

   This pretty much exactly what you'd expect. Takes an array(*) of data, orders it ascending (smallest first) according the ordinal (ASCII**) values of the characters in the strings:

    print for sort qw[ 12 a123 a122 A123 B123 Ab123 aB123 456 1A23 1a23 ]
   +;;
   12          ## ord('1') == 49, ord('2') == 50
   1A23        ##                 ord('A') == 65  so this comes after.
   1a23        ##                 ord('a') == 97                  "
   456         ## ord('4') == 52                                  "
   A123        ## ord('A') == 65, ord('1') == 49                  "
   Ab123       ##                 ord('b') == 98                  "
   B123        ## etc.
   a122
   a123
   aB123
   [download]

   *actually a list, but ignore that for now.

   **if your data is unicode, then the unicode ordinal values are used.

2. my @reversedSordedAlpha = sort{ $b cmp $a } @alphaData;

   Here we want the data order in descending (largest first) sequence, so we have(*) to use code block to alter the default ordering.

   The { $b cmp $a } but of that tells sort that we wish to perform the ordering ourselves instead of using the default as we did in 1 above (which is equivalent to { $a cmp $b }). This says that for each pair of values in the input, Perl passes them to us (as $a and $b), and we perform a comparison and return

   • -1 if $a is less than $b
   • 1 if $a is greater than $b
   • 0 if $a equals $b

   With this information, sort can correctly do what it needs to do to reorder the input appropriately.

   By using the built-in cmp function that is specifically designed for comparing strings and producing these values, we achieve the result we are after.

   Supplying the arguments $a & $b to the function in reverse order has the effect of reverseing the sort.

   However, if we use cmp on numeric data, we do not get the effect we want:

   print for sort{ $b cmp $a } qw[ 1 10 100 2 20 21 3 300 ];;
   300
   3
   21
   20
   2
   100
   10
   1
   [download]

   For numeric data we need to use the other built-in comparison operator <=>.

   *we can also use reverse, and that may actually be quicker, but this is a tutorial and this way demostrates the point I wish to make.

3. my @reverseSortedNumbers = sort { $b <=> $a } @numbers;

   Using <=> produces the desired result.

   print for sort{ $b <=> $a } qw[ 1 10 100 2 20 21 3 300 ];
   300
   100
   21
   20
   10
   3
   2
   1
   [download]

   The difference is that <=> compares the (binary) numerical value of it's arguments, instead of the bytewise string comparisons of the ASCII representation that cmp does.

4. my @sortedNumbers = sort{ $a <=> $b } @numbers;

   And for an ascending numerical sort, we just pass the parameters to <=> in the 'right' order.

How sort actually works doesn't really matter. That it is about as fast as you are likely to get, is built-in to langauge so always available and understands Perl internals does.

So, sorting data when you want to sort according the the entire value of each element of the array or list is easy. It gets a little more complex when you want to sort the elements by a sub field of each element.

For example, say you have a set of ids (A123 B421 C987 etc.) and you want to order them by just the numeric part, then you need to extract that part before supplying it to the appropriate comparison function:

print for sort{ 
    substr( $a, 1 ) <=> substr( $b, 1 ) 
} qw[ A473 B659 C123 D222 E001 ];;
E001
C123
D222
A473
B659
[download]

This works fine, but each element will be passed to the comparison block multiple times, and that means we are extracting the sort field from each element multiple times, which can slow things down. For more complex cases, like your dates problem, this could be significant. The purposes of the "advanced sorting" mechanisms is to reduce this slowdown by performing the extraction of the significant data from each input element once only.

The ST

One mechanism, and possibly the simplest to understand, it merlyn's ST (Schwartzian Transform). This works by pre-processing the elements to extract the fields and package them into anonymous arrays. The list of annonymous arrays are then sorted and finally the original elements are recovered from the list of sorted anonymous arrays and stored into the sorted array.

## Build an array of anonymous arrays, 
## each of which contains the sort field and the original element.
@anons = map{ [ substr( $_, 1 ) , $_ ] } qw[ A473 B659 C123 D222 E001 
+];;
print Dumper \@anons;;
$VAR1 = [
    ['473','A473'],['659','B659'],['123','C123'],
    ['222','D222'],['001','E001']
];

## Now sort the anons 
## by comparing the extracted fields from within the anonymous arrays.
@sortedAnons = sort{ $a->[ 0 ] <=> $b->[ 0 ] } @anons;;
print Dumper \@sortedAnons;;
$VAR1 = [
    ['001','E001'],[123,'C123'],[222,'D222'],
    [473,'A473'],[659,'B659']
];

## Finally, build the required sorted array 
## by extracting the original elements discarding the sort fields.
@sorted = map{ $_->[ 1 ] } @sortedAnons;;
print Dumper \@sorted;;

$VAR1 = ['E001','C123','D222','A473','B659'];
[download]

This is quite simple to follow and can be coded in a more compact form, by combining the 3 steps into a single statement and doing away with the intermediate arrays:

@sorted = map{ 
    $_->[1] 
} sort{ 
   $a->[0] <=> $b->[0] 
} map{ 
    [ substr( $_, 1 ), $_ ] 
} qw[ A473 B659 C123 D222 E001 ];;

print Dumper @sorted;;
VAR1 = 'E001'; $VAR2 = 'C123'; $VAR3 = 'D222'; $VAR4 = 'A473'; $VAR5 =
+ 'B659';
[download]

This is identical to the previous example, but more compact. It can also be formatted as a single line, though that will usually mean that it extends beyond the boundary at which PM does it's dumb wrapping. It can also be laid out in several different ways to that I've shown, but I find that this makes the three signifcant steps of the algorithm clearly delineated, by indenting the contents of the code blocks just as you would for any other block of code. Eg. The body of if and while statements etc. I like this consistency.

The efficiency of the ST comes from only performing the extractions of the field data once. Indexing the anonymous arrays is very efficient and so the sorting and reassembly doesn't costs much extra. It also extends to sorting multiple fields in an obvious way:

print for map{ 
    $_->[2] 
} sort{ 
    $a->[0] <=> $b->[0]  || $a->[1] cmp $b->[1] 
} map{ 
    [ substr( $_, 1 ), substr( $_, 0, 1 ),  $_ ] 
} qw[ A473 B437 B659 C659 C123 D123 D222 E222 E001 A001 ];;
A001
E001
C123
D123
D222
E222
B437
A473
B659
C659
[download]

Here we've ordered the data according to the numeric field as before, but this time we've used the alpha field to 'tiebreak' values when the numeric values are the same. It's easy to see how this can be further extended to handle as many fields of any type we need. This simple, obvious extension mechanism is the great strength of the ST.

The caveats

The downside of the ST is that for large datasets, the creation and destruction of all the small anonymous arrays can itself prove to be fairly expensive of time and memory.

It's also the case that calling back into Perl code via the sort comparison block imposes a significant time cost. (Don't worry about this for the simple cases of sort{ $a <=> } ... and sort{ $b cmp $a } shown above, as Perl has optimisations to recognise these simple cases, and it doesn't actually do a callback at all).

But for more complex sorting, these callbacks are expensive, and if you can avoid them, it will save some considerable time.

The GRT

This is where the (Guttman Rossler Transform) comes in. The basic idea here is that instead of building an anonymous array in the pre-processing stage, we prepend the field data to the front of the string; sort the strings; then strip the bit we stuck on the front back off.

Going back to the simpler example of a field sort above, we can construct the GRT as follows:

print for map{ 
    ## Chop off the bit we added.
    substr( $_, 3 ) 
} sort map{           ## Note: No comparison block callback.
    ## Extract the field as before, but concatenate it with the origin
+al element
    ## instead of building an anonymous array containing both elements
+.
    substr( $_, 1 ) . $_ 
} qw[ A473 B659 C123 D222 E001 ];;

E001
C123
D222
A473
B659
[download]

A cheat

This is actually something of a cheat of a GRT. It only works because in my carefully constructed example data, the numeric fields all have the same number of digits, with smaller values having leading zeros. Whilst this works fine, and makes the algorithm easy to follow (try adding print statements inside the code blocks to follow what is going on), real life data is rarely so accommodating. Whilst you could use sprintf to add leading zeros and so make your ascii encoded numeric fields sort correctly using the string comparisons (cmp), it turns out that there is a better (faster) way.

That way is to use pack to convert the numeric fields into binary values that will sort correctly using a string comparison function. It is convenient that binary encode integers (NOTE:In 'network' format only. That is 'N'&'n' *NOT* 'V'&'v') will sort correctly using a string comparison function. As will floating point data in IEEE formats (the format used internally by Perl on most but not all systems).

So, using pack, the previous example becomes:

print for map{ 
    unpack 'x[N] A*', $_ 
} sort map{ 
    pack 'N A*', substr( $_, 1 ), $_ 
} qw[ A473 B659 C123 D222 E001 ];;
E001
C123
D222
A473
B659
[download]

That may not look so very different from the previous version, but the big advantage is that it will handle any integer values correctly, whereas with the previous version, you need to know how big the largest numeric field is, so that you can add the correct number of leading zeroes.

It also trivially extends to handle the two fields example shown above for the ST:

print for map{ 
    unpack 'x[NA1]A*', $_ 
} sort map{ 
    pack 'NA1 A*', substr( $_, 1 ), substr( $_, 0, 1 ),  $_ 
} qw[ A473 B437 B659 C659 C123 D123 D222 E222 E001 A001 ];
A001
E001
C123
D123
D222
E222
B437
A473
B659
C659
[download]

The pattern

Hopefully, the pattern is becoming obvious. Use pack with appropriate templates 'N', 'n', 'd' etc. to prepend the sort field data to the strings in the order or precedence. Then use unpack and the same template as you used for the sort fields, but wrapped in 'x[...]' to strip the prefix off and recover the original elements.

Hmmm. Is that any clearer than the existing explanations?