[Python-Dev] Sorting

[Scott Gilbert]

--- Tim Peters <tim.one@comcast.net> wrote:
> In an effort to save time on email (ya, right ...), I wrote up a pretty
> detailed overview of the "timsort" algorithm.  It's attached.
> 
> all-will-be-revealed-ly y'rs  - tim
>
> [Interesting stuff deleted.]
>

I'm curious if there is any literature that you've come across, or if
you've done any experiments with merging more than two parts at a time.  So
instead of merging like such:

  A B C D E F G H I J K L
  AB  CD  EF  GH  IJ  KL
  ABCD    EFGH    IJKL
  ABCDEFGH        IJKL
  ABCDEFGHIJKL

You were to merge

  A B C D E F G H I J K L
  ABC   DEF   GHI   JKL
  ABCDEF      GHIJKL
  ABCDEFGHIJKL

(I realize that your merges are based on the lengths of the subsequences,
but you get the point.)

My thinking is that many machines (probably yours for instance) have a
cache that is 4-way associative, so merging only 2 blocks at a time might
not be using the cache as well as it could.  Also, changing from merging 2
blocks to 3 or 4 blocks at a time would change the number of passes you
have to make (the log part of N*log(N)).

It's quite possible that this isn't worth the trade off in complexity and
space (or your time :-).  Keeping track of comparisons that you've already
made could get ugly, and your temp space requirement would go from N/2 to
possibly 3N/4...  But since you're diving so deeply into this problem, I
figured I'd throw it out there.

OTOH, this could be close to the speedup that heavily optimized FFT algs
get when they go from radix-2 to radix-4.   Just thinking out loud...






__________________________________________________
Do You Yahoo!?
Yahoo! Health - Feel better, live better
http://health.yahoo.com