Under what conditions is a specific sorting algorithm actually the fastest one?
1) When implemented in a parallel way in hardware, does it need to have a reasonably low latency while requiring as few gates as possible? Yes -> use a bitonic sorter or Batcher odd-even mergesort, latency is $\Theta(\log(n)^2)$ and the number of comparators and multiplexers is $\Theta(n \cdot \log(n)^2)$.
2) How many different values can each element have? Cans every possible value have assigned a unique place in memory or cache Yes -> use count sort or radix sort, those usually have a linear runtime of $\Theta(n \cdot k)$ (count sort) or $\Theta(n \cdot m)$ (bucket sort) but slow down for a large number of different values, as $k=2^{#number_of_Possible_values}$ and $m = #maximum_length_of_keys$.
3) Does the underlying data structure consist of linked elements? Yes -> allways use in place merge sort. There are both easy to implement fixed size or adaptive(aka natural) bottom-up in place merge sorts of different arities for linked data structures, and since they never require copying the entire data in each step and they never require recursions either, they are faster than any other general comparision-based sorts, even faster than quick sort.
4) Does the sorting need to be stable? Yes -> use merge sort, either in place or not, fixed-size or adaptive, depending on the underlying data structure and the kind of data to be expected, even in cases where quick sort would otherwise be preferred, as stabilizing an arbitrary sorting algorithm requires $\Theta(n)$ additional memory in the worst case consisting of original indexes, which also needs to be kept in sync with each swap that is to be performed on the input data, so that every performance gain that quick sort might have over merge sort is probably thwarted.
5) Can the size of the underlying data be bound to a small to medium size? e.g. Is n < 10,000...100,000,000 (depending on the underlying architecture and data structure)? Yes -> use bitonic sort or Batcher odd-even mergesort. <PERSON> 1)
6) Can you spare another $\Theta(n)$ memory? Yes -> a) Does the input data consist of large pieces of already sorted sequential data? -> use adaptive (aka natural) merge sort or tim sort Yes -> b) Does the input data mostly consist of elements that are almost in the correct place? -> use bubble sort or insertion sort. If you fear their $\Theta(n^2)$ time complexity (which is pathological for almost sorted data), maybe consider switching to shell sort with an (almost) asymptotically optimal sequence of gaps, some sequences that yield $\Theta(n \cdot \log(n)^2)$ worst case run time are known, or maybe try comb sort. I'm not sure either shell sort or comb sort would perform reasonably good in practice.
No -> 7) Can you spare another $\Theta(\log(n))$ memory? Yes -> a) Does the undelying data structure allow for directed sequential access or better? Yes -> Does it allow only a single sequence of read/write accesses at a time up till the end of the data has been reached (e.g. 143
directed tape access)? Yes -> i) use merge sort, but there is no obvious way to make this case in place, so it may require additional $\Theta(n)$ memory. But if you have time and the balls to do it, there is a way to merge 2 arrays in $\Theta(n)$ time using only $\Theta(\log(n))$ space in a stable way, according to <PERSON> "The Art of Computer Programming, Volume 3: Sorting and Searching", exercise 5.5.3. states that there is an algorithm by <PERSON> that does so. However, I doubt this would be any faster than the naive mergesort version or the quicksort from the case above. No, it allows multiple simultaneous accesses to a sequence of data (e.g. is not a tape drive) -> ii) use quicksort, for practical purposes I would recommend either a randomized or an approximated median one. If you are wary of pathological $\Theta(n^2)$ cases, consider using intro sort. 143