Sorting : Algorithm Performance
Recently I was puzzling the following question:
What sort would you use if you required tight
max time bounds and wanted highly regular
performance?
Discussion
There were some answers but nothing beats implementing and measuring for yourself.
Inputs
- Constant value : [1,1,1,…]
- Sorted : [1,2,3,…]
- Reverse sorted: [N, N-1, N-2, …]
- Random: […]
- Interleaved : [Constant, Sorted, Reverse-sorted, Random, …]
Algorithms
- Insertion Sort
- Quicksort
- Heap Sort
- Bucket Sort
Input Data
Results
- ‘heapsort’ had the most consistent performance
- ‘quicksort’ had the fastest performance
- ‘quicksort’ had the worst performance
Determining which sorting algorithm is ‘best’ for a given use case actually depends on your requirements. If you need the fastest sorter possible, then that’s probably quicksort. But if you need good overall performance for a wide variety of input types, you’re probably going to want heapsort. The full analysis is captured here as a Jupyter Notebook (with lots of pretty graphs):