When a list contains two or more values that are exactly the same, how do you compare those values?
In some applications, data with the same value may use additional information (what results in equal
values not being the same).
So, a stable / unstable sort algorithm may be relevant, for some applications.
Quicksort can be implemented as a stable sort algorithm, but with some additional storage space.
(5) Advanced concepts: Median.
This tutorial uses average as pivot. But the pivot could have another definition.
The choice of pivot defines the size of each sublist. This can result in undesired unbalanced lists.
The perfect pivot would be the median of a list.
But the effort to calculate the median would make Quicksort slower.
So, in practice, some other value is defined as pivot: as near to the median as possible, and fast to
calculate.
Originally in 1959, Tony Hoare
implemented Quicksort using the first (or last) element of a list as pivot. The algorithm usually works fine
with this choice.