Sorting Lists using 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:

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);
    }
}
Feedback is always welcome! If you'd like to get in touch with me concerning the contents of this article, please use Twitter.