Sorting Lists using Perl
Published on 07 Jun 2004Tags #Perl
Unfortunately, the default perl sort algorithm was changed to Mergesort (formerly Quicksort) which does not provide in-place sorting as Quicksort does. This fact and some obscure stupidity in the implementation causes the space requirements to be much higher than the size of the original list.
Before jumping to quick conclusions whether it makes sense to call me a blind idiot or to use my code, please be aware of some theoretical fact:
-
Average case time complexity of Quicksort: O(n log n)
-
Worst case time complexity of Quicksort: O(n^2)
-
Time complexity of Mergesort: O(n log n)
-
Space requirement of Quicksort: in-place … O(n)
-
Space requirement of Mergesort: twice the input size … O(2n)
(Although this reduces to O(n), it is important to note that a helper list of the same size as the input list is required!)
Unfortunately, the perl implementation of Mergesort seems to be flawed (at best), because my tests indicated that it required several time the size of the input list.
Thus, I implemented the Quicksort algorithm because I needed to sort very large lists without the enormous blowup. The algorithm is also included in my Perl Math Module.
&quicksort(@list, 0, $#list)
sub quicksort {
my $ref_data = shift;
my $p = shift;
my $r = shift;
if ($p < $r) {
my $temp;
my $q;
my $x = $ref_data->[$p];
my $i = $p - 1;
my $j = $r + 1;
while (1) {
do {
--$j;
} until ($ref_data->[$j] <= $x);
do {
++$i;
} until ($ref_data->[$i] >= $x);
if ($i < $j) {
$temp = $ref_data->[$i];
$ref_data->[$i] = $ref_data->[$j];
$ref_data->[$j] = $temp;
} else {
$q = $j;
last;
}
}
&quicksort($ref_data, $p, $q);
&quicksort($ref_data, $q + 1, $r);
}
}