Best way to merge/sort two sorted lists?...

[Aaron Watters]

On Dec 6, 9:51 pm, "Terry Reedy" <tjre... at udel.edu> wrote:
> "Aaron Watters" <aaron.watt... at gmail.com> wrote in message
> The current version of list.sort (timsort) was designed to take advantage
> of pre-existing order.  It should discover the 2 sorted sublists and merge
> them together.  It will not really re-sort the way it would with random
> data.
>
> A psyco/Python version can be faster only because it avoids the comparisons
> need to discover the existing sorted sublists.

I'm not sure about psyco, but I bet a tuned C implementation
can get more than another factor of 2-3 better, and it wouldn't
be that long either (except I'd have to stretch some unused
brain muscles).  This is especially true since the functionality
I need is slightly more complex than this (I need to sort keys
and values together, preferably without making a list of pairs
to do it, and I need "remainder" lists where the key values do
not overlap).   This is what nucular index builds spend all their
time doing, so it would have a big impact, I think.
Cool stuff.  Fun too.
   -- Aaron Watters