An “intuitive” view of how TIMSORT works is shown at: http://corte.si/posts/code/timsort/

Loren P Meissner

“Truth depends on a quest to discover what’s really out there, what really happened. It isn’t given over to you by simply following a set of rules.” – Errol Morris

“Math education is not something you can dictate. The way to make a tree grow is not to yank it upward by the branches. ” – Professor Hung-Hsi Wu, UC Berkeley

**From:** Fortran 90 List [mailto:[log in to unmask]] **On Behalf Of **Walt Brainerd**Sent:** Wednesday, February 08, 2012 11:54 AM**To:** [log in to unmask]**Subject:** Re: Sorting large array

On Wed, Feb 8, 2012 at 11:50 AM, Sturla Molden <[log in to unmask]> wrote:

On 08.02.2012 17:44, Loren P Meissner wrote:

BUT WITH QUICKSORT, WATCH OUT FOR WORST CASE!

It might be of interest that timsort is O(n) for common cases where quicksort is O(n**2), and worst-case for timsort is O(n log n).

Sturla

I believe one can prove that the best sort (of the sort we are thinking of)

is O(n log n).

And there are nonrecursive versions of quicksort around.

--

Walt Brainerd