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

[Neil Cerutti]

On 2007-12-06, Aaron Watters <aaron.watters at gmail.com> wrote:
> ...is to forget they are sorted???
>
> While trying to optimize some NUCULAR libraries I discovered
> that the best way to merge 2 sorted lists together
> into a new sorted list is to just append
> them and re-sort.  The following test case demonstrates this.
> It can be criticized in many ways: it only tests lists of the same
> size,
> it only uses "hashed" data, etcetera...
> Still, my testing shows "resort everything" is consistently
> two times faster than an explicit python merge even for fairly large
> data.
>
> I'm beginning to think
> a "sorted list merger" might make a nice tiny extension module
> (at least for my purposes).
>
> See timing demonstration code below.  Let me know if there
> is a better way or if the test is fatally flawed, please.
>
>   --- Aaron Watters
>====
> http://www.xfeedme.com/nucular/pydistro.py/go?FREETEXT=greedy+bastard
>
>==========snip: test code below
> "test different ways to merge two sorted lists"
>
> def ObviousMerge(L1, L2):
<SNIP>
> def AggregateTailMerge(L1, L2):
<SNIP>

Your merge functions are pretty complex; here's a simpler,
obvious solution:

def merge_sorted(a, b):
    """Merge two sorted lists into a new sorted list.

    >>> merge_sorted(range(10), range(5))
    [0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 7, 8, 9]

    >>> merge_sorted(range(5), range(10))
    [0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 7, 8, 9]

    >>> merge_sorted(range(3), [])
    [0, 1, 2]

    >>> merge_sorted([], range(3))
    [0, 1, 2]

    >>> merge_sorted([], [])
    []
    """
    rval = []
    aix, bix = 0, 0
    astop, bstop = len(a), len(b)
    while aix < astop and bix < bstop:
        if a[aix] < b[bix]:
            rval.append(a[aix])
            aix += 1
        else:
            rval.append(b[bix])
            bix += 1
    while aix < astop:
        rval.append(a[aix])
        aix += 1
    while bix < bstop:
        rval.append(b[bix])
        bix += 1
    return rval

It should beat ResortEverything consistently once the lists
become larger than a certain size. Do you get better results at
all with the above function?

-- 
Neil Cerutti
The audience is asked to remain seated until the end of the recession.
--Church Bulletin Blooper