>> Who the heck can say sth about the imput (that it may be like "pre-sorted" ?!) Lots of real world (as opposed to synthetic random test data) may be already

>> Who the heck can say sth about the imput (that it may be like "pre-sorted" ?!) Lots of real world (as opposed to synthetic random test data) may be already ordered or contain ordered subsequences. One wants to run a sorting algorithm to guarantee the data is sorted, and thus performance on pre-sorted data is important. This is why Timsort is the default sort in Python and Java. http://en.m.wikipedia.org/wiki/Timsort http://en.m.wikipedia.org/wiki/Timsort It is the worst case performance for quick sort.