What sort would you use if you required tight max time bounds and wanted highly regular performance?
There were some answers but nothing beats implementing and measuring for yourself.
- Constant value : [1,1,1,…]
- Sorted : [1,2,3,…]
- Reverse sorted: [N, N-1, N-2, …]
- Random: […]
- Interleaved : [Constant, Sorted, Reverse-sorted, Random, …]
- Insertion Sort
- Heap Sort
- Bucket Sort
- ‘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):