You only realize the difference when you compare things. I sometimes thought “how fast built-in Perl sort really is?”, but never got to any comparison (finally got to some sort algorithms research). Well, no surprises, of course (and my implementations are quite sub-optimal), but still (sorta FTR – this is a sort of 10K-element array filled with int representations of rand(10000) values):
- perl: 0.00242
- quicksort: 0.097454
- mergesort: 0.115439
- insert sort: 8.223053
Another FTR – Perl (since 5.8) has both quicksort and mergesort, although as I understand quicksort is still used by default – just shuffling (big?) arrays to save from worst-case scenario in pre-sorted case. You can change the sort algorithm though with this (from http://perldoc.perl.org/sort.html):
- use sort ‘stable’; # guarantee stability
- use sort ‘_quicksort’; # use a quicksort algorithm
- use sort ‘_mergesort’; # use a mergesort algorithm
- use sort ‘defaults’; # revert to default behavior
- no sort ‘stable’; # stability not important
Like, if you need a “stable” sort (which mergesort is) – when same elements preserve their initial order.