And now including the lines that do not contain the word "algorithm":
Perl 5.6 and earlier used a quicksort algorithm to implement
sort. That algorithm was not stable, and could go quadratic.
(A stable sort preserves the input order of elements that
compare equal. Although quicksort’s run time is O(NlogN) when
averaged over all arrays of length N, the time can be O(N**2),
quadratic behavior, for some inputs.) In 5.7, the quicksort
implementation was replaced with a stable mergesort algorithm
whose worst-case behavior is O(NlogN). But benchmarks
indicated that for some inputs, on some platforms, the original
quicksort was faster. 5.8 has a sort pragma for limited
control of the sort. Its rather blunt control of the
underlying algorithm may not persist into future Perls, but the
ability to characterize the input or output in implementation
independent ways quite probably will. See sort.
