sorting many arrays from one...

[Alex Martelli]

Tim Peters wrote:
        ...
>> (lists that are close to being ordered
> 
> Unfortunately, it's only some lists that are close to being ordered,
> although I believe it catches the most frequent real-life cases of that.

Right.  The only extra case I've often wished it handled (defining
"often" as "more than once":-) is when the FIRST element is out of
order and all the rest are OK.  That happens in mergesorting huge
streams, in the core merge loop:

    while streams:
        yield streams[0][0]
        try:
            streams[0][0] = streams[0][2]()
        except StopIteration:
            del streams[0]
        else:
            streams.sort()  # this is the first-maybe-OOO sort

The "streams" auxiliary list is originally built from the sequence X
of already-sorted streams as:

streams = [ [X[i].next(), i, X[i].next] for i in range(len(X)) ]

Normally N==len(streams) isn't all that big, and I COULD make each
leg of the "while streams:" loop O(N) anyway by using knowledge
about _which_ special cases method sort is so good at -- changing
the else clause into:

        else:
            streams.append(streams.pop(0))
            streams.sort() # the maybe-OOO item is now *LAST*...

but that's not all that pleasant -- I'd do it only in emergencies...


Alex