The compare function is called repeatedly with different elements.

my @numbers = (7, 12, 49, 44);
my @sorted =
    sort {
        print("Comparing $a with $b...\n");
        $a <=> $b
    }
    @numbers;
[download]

Comparing 7 with 12...
Comparing 49 with 44...
Comparing 7 with 44...
Comparing 44 with 12...
[download]

It only does the comparisons it deems necessary. As you can see, 7 was never compared against 49 directly in the example.

Perl currently uses merge sort unless told otherwise.

Complex13:

You may have seen a bubble sort, it goes something like this:

my @vars = (7, 12, 49, 44);
sub bubble_sort {
   for my $i (1 .. $#vars) {
      for my $j (0 .. $i-1) {
         print "vars[$i]=$vars[i], vars[$j]=$vars[j]: ";
         if ($vars[i]<$vars[j]) {
            print "vars[$i]<vars[$j], swapping!\n";
            my $t=$vars[i]; $vars[$i]=$vars[$j]; $vars[$j]=$t;
         }
         else {
            print "vars[$i]>=vars[$j], no swap needed.\n";
         }
      }
   }
}
[download]

I put in print statements to help you see how it would work. There are many different sorting algorithms, but this one is pretty easy to read and understand. As you can see, the sort simply compares elements in the list and swaps them depending on their order. The bubble sort above should sort from the lowest value to the highest value. But if you wanted to sort in the other direction, you'd need to change the if statement. Also, if you wanted to sort different types of items, you'd need to change the if statement.

So what they did was to let you provide your own comparison function, so you can sort any items you want in any order. If we do that to our bubble sort, and take out the print statements, it could look like this:

my @vars = (7, 12, 49, 44);
sub bubble_sort {
   my $rfunc = shift;
   for my $i (1 .. $#vars) {
      for my $j (0 .. $i-1) {
         if (&($rfunc)($vars[i], $vars[j])) {
            my $t=$vars[i]; $vars[$i]=$vars[$j]; $vars[$j]=$t;
         }
      }
   }
}
[download]

So for the updated bubble_sort, we have to pass it a function that will return true if we want it to swap the elements in the list, and false if they don't need to be swapped. So we can sort in ascending order like this:

sub ascending {
   my ($left, $right) = @_;
   return $right > $left;
}

bubble_sort(\ascending);
[download]

You get the picture. But you don't always want to clutter your program with a zillion trivial functions that you use only once. It will clutter your namespace (oops--I can't call that function ascending, I've already used it for something else!). So rather than creating a function by name, we can create an anonymous subroutine, and pass that to our bubble sort:

bubble_sort(sub { my ($left, $right)=@_; return $right>$left });
[download]

That's a lot better, right? Well in perl you don't even have to pass an anonymous subroutine. Perl lets you pass references to code, too, which gets you the rest of the way to the built-in sort function.

It's late here, so I glossed over quite a few things. I'm sure perl doesn't use the bubble sort, but that's just a detail. I didn't worry about passing the list to be sorted, as I didn't want to clutter up the coded with the details of the extra parameters and such. But I hope it's complete enough to get the point across. Finally, I didn't run any of this code, either, so it may have an error or two.

Let me know if it's clear enough, I'll be glad to give further details if I left anything out that you needed.

...roboticus

When your only tool is a hammer, all problems look like your thumb.

Update: As Khen1950x mentions below, the sort built-in expects a comparison function that returns -1, 0, or +1. I got away with true/false because the bubble sort didn't need any further information. But some more advanced sorting algorithms need/want a little more information.

Depending on your version of perl, it may use a quicksort or a mergesort. (Google those algorithms and you'll surely find some very good explanations of both.) Newer versions give you some say over which is used via the sort pragma.

Note that the mergesort implemented by Perl isn't the stock mergesort you see in the textbooks.

It's a special version of mergesort that takes advantage of runs of already sorted (or reversed sorted) items. While at the same time making sure the sort is stable. This makes sorting of (almost) sorted lists faster than stock mergesort would give you.

The quicksort implemented by Perl has some defenses against poor performance as well. Traditional quicksort is behaves quite poorly on sorted lists (with naive textbook implementation even going quadratic). Perls quicksort does some smart pivot picking (middle-of-three, IIRC) - but it can still behave badly on pipe-organ shaped lists. As an extra defense, if quicksort is picked, and the list is larger than a certain size, the list will be shuffled first.

Do you know whether Perl's mergesort has borrowed a lot of ideas from Python's timsort?

0 is returned if $a and $b are equal.
1 is returned if $a is greater than $b.
-1 is returned if $a is less than $b.

BrowserUk wrote A brief tutorial on Perl's native sorting facilities. It'll help.

Your observation seems to match the sort documenattion

There is a series of definitive computer-science textbooks, written by Dr. Knuth, and one of the volumes is entitled, Sorting and Searching.   Although many of the pages are scribbled with mathematical formulations and other strange magick which is far beyond my ken, it is nevertheless true that “sorting and searching” are, and always have been, probably the most-studied types of algorithms in all of computer science (with the possible exception of data encryption).