2012-05-05, 03:55 AM
Ah, yes. Duplicate values would do it.
The other thing is, if you anticipate having to sort arrays with many duplicate values, you can also treat values equal to the pivot as a third "partition" and not recurse on it at all. This requires a bit more overhead but would yield O(n) time on an array of all duplicates, which is the best possible result.
The other thing is, if you anticipate having to sort arrays with many duplicate values, you can also treat values equal to the pivot as a third "partition" and not recurse on it at all. This requires a bit more overhead but would yield O(n) time on an array of all duplicates, which is the best possible result.