Under the hood, Perl’s sort() function uses the quicksort algorithm, which we’ll describe later in the chapter. This is a standard sorting algorithm, provided by most operating systems as qsort(3).[12] In Versions 5.004_05 and higher, Perl uses its own quicksort implementation instead of the one provided by the operating system. Two primary motivations were behind this change. First, the implementation has been highly optimized for Perl’s particular uses.

In Perl versions 5.6 and earlier the quicksort algorithm was used to implement sort(), but in Perl 5.8 a mergesort algorithm was also made available, mainly to guarantee worst case O(N log N) behaviour: the worst case of quicksort is O(N**2). In Perl 5.8 and later, quicksort defends against quadratic behaviour by shuffling large arrays before sorting.