Print

Print


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