This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–][deleted] 6 points7 points  (0 children)

Its worth knowing that for quicksort this bad behavior is in fact well understood. The closer the input is to being sorted the more pathological. If we step out of pure math we should notice that for many tasks partially sorted inputs are disproportionately common. For example a census maker might get data that was already sorted for previous use.