Some historic quick-sort mis-implementations had O(n^2) runtime when trying to sort constant data (all keys equal, the effect was due to not picking the partiti

Some historic quick-sort mis-implementations had O(n^2) runtime when trying to sort constant data (all keys equal, the effect was due to not picking the partition carefully in that case). See: http://www.win-vector.com/blog/2008/04/sorting-in-anger/ http://www.win-vector.com/blog/2008/04/sorting-in-anger/