 |
 |
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