sorting many arrays from one...
Alex Martelli
aleax at aleax.it
Thu Jul 11 07:25:03 EDT 2002
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
More information about the Python-list
mailing list