Data Structures & Algorithms Lecture Notes

3 December 2010 • Faster Sorting

To get a better idea about mergesort’s value, here’s the same graphs without quicksort:

sorted- vs. unsorted-int mergesort

sorted- vs. unsorted-point mergesort
Sorted data is more cache friendly than is unsorted data, which is why mergesort performs slightly better when sorting sorted data

Finally, here’s a comparison sort times for clever-pivot quicksort and mergesort on sorted data

quicksort vs mergesort on sorted ints

quicksort vs mergesort on sorted points
The usual conclusion is that, in general, the extra space isn’t worth it, and that clever-pivot quicksort wins.
This page last modified on 24 January 2006.