On the Sorting Algorithms website, the following claim is made:
The ideal sorting algorithm would have the following properties:
- Stable: Equal keys aren't reordered.
- Operates in place, requiring $O(1)$ extra space.
- Worst-case $O(n\cdot\lg(n))$ key comparisons.
- Worst-case $O(n)$ swaps.
- Adaptive: Speeds up to $O(n)$ when data is nearly sorted or when there are few unique keys.
There is no algorithm that has all of these properties, and so the choice of sorting algorithm depends on the application.
My question is, is it true that
there is no [sorting] algorithm that has all of these properties
and if so, why? What is it about these properties that makes all of them simultaneously impossible to fulfill?