QSort in D: is this best?

[bearophile]

Philippe Sigaud:
> merge2 is greedy and works only for two ranges (hence it's name), but I have
> a templated, predicate-aliased, lazy, n-ranges version called merge in the
> module.

This is how merge is implemented in the heapq module of the Python standard lib:

def merge(*iterables):
    h = []
    for itnum, it in enumerate(map(iter, iterables)):
        try:
            next = it.next
            h.append([next(), itnum, next])
        except StopIteration:
            pass
    heapify(h)

    while True:
        try:
            while True:
                v, itnum, next = s = h[0] # raises IndexError when h is empty
                yield v
                s[0] = next()             # raises StopIteration when exhausted
                heapreplace(h, s)         # restore heap condition
        except StopIteration:
            heappop(h)                    # remove empty iterator
        except IndexError:
            return


Bye,
bearophile