efficient idiomatic queue?

[Raymond Hettinger]

"Paul Rubin" <phr-n2002a at nightsong.com> wrote in message
news:7xpu4cglp3.fsf at ruckus.brouhaha.com...
> How's this (untested; uses nested scopes).  It uses extra temp space
> the size of the input, but runs in the correct order time.
>
> def merge(a,b):
>    ia, ib = 0, 0    # indices
>    def next():
>       # peel next element off a or b.
>       m = 0         # selector between a and b
>       if ia < len(a) and ib < len(b):
>          m = a[ia] < b[ib]
>       else:
>          m = ia >= len(a)
>
>       if m == 0:
>          x, ia = a[ia], ia+1
>       else:
>          # if both a and b are exhausted, this throws IndexError.
>          x, ib = b[ib], ib+1
>    return x
>
>    result = []
>    try:
>       while 1:
>          result.append(next())
>    except IndexError:
>       return result

FWIW, here's my crack at the same thing:

def merge(left, right):
    ans = []
    try:
        while 1:
            ans.append( (left[-1] > right[-1] and left or right ).pop() )
    except IndexError:
        ans.reverse()
        return left + right + ans

def msort(ds):
    if len(ds) <= 1: return ds
    mid = len(ds) // 2
    return merge( ms(ds[:mid]), ms(ds[mid:]) )


Raymond Hettinger