None. It depends on the circumstances.
Naturally, the next question is: Which one must be used in each case?
The best choice is almost always the implementation that comes with the language you are using.
In some cases you can choose among the following options:
- Stable sort. Generally requires O(N) additional memory, that is, an amount proportional to the data being sorted.
- Non-stable sort. Requires very little additional memory, but does not respect the previous order of the elements considered equal to each other.
More details in: stable sort
and in: “big O” notation.
In C++, for instance, you can choose between std::sort and std::stable_sort.
In the field of sorting with little additional memory there have been several favorites along the history: ShellSort (1959), quicksort (1960), heapsort (1964) and more recently introsort (1997), which is a hybrid of quicksort, heapsort and insertion sort.
Mergesort (1945) dominated many years in the field of stable sorting. Its replacement seems to be Timsort (2002). It is also a hybrid, this time of mergesort, insertion sort and a few more tricks.
I will discuss the few cases where it makes sense (in my opinion) to tailor your own implementation of a sorting algorithm. But I’ll do it later ;-)