How does Timsort work O.o ?

Question

anonymous · Answer

i really dont know. sorry. wait... are you talking about MATH???

mathmate · Answer

Timsort sounds like the best of all worlds, it performs at O(nlog(n))in the average AND worst case, and O(n) in the best case (already sorted), while Quicksort performs O(nlog(n)) in the best and average case, and O(n^2) in the worst case (already sorted).

It does this by identifying if the array is already sorted, and change strategy as the data changes.

There is a price for everything, though.  While quicksort take nlog(n) space, Timsort takes a space of n!

mathmate · Answer

Sorry, the last ! is an exclamation mark, not a factorial!

anonymous · Answer

lol I thought it was factorial

anonymous · Answer

but that's smaller than nlog(n), isn;t it?

mathmate · Answer

You're right!  I made a mistake for quick sort, which takes log(n), compared to n for timsort.