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