Hpw make lists that are easy to sort.

[Anton Vredegoor]

Paul Rubin wrote:

> Oh, I see what you mean.  I don't see an obvious faster way to do it
> and I don't have the feeling that one necessarily exists.  As someone
> mentioned, you could do an n-way merge, which at least avoids using
> quadratic memory.  Here's a version using Frederik Lundh's trick of
> representing a lazy list as its head plus the generator for the tail:

That's a beautiful trick! I was just exploring some idea about 
traversing the matrix starting from the upper left and ending at the 
lower right by forming some kind of wave like front line. It's currently 
very slow but I hope it can be polished a bit.

Also I was trying to figure out if it could have any advantage over the 
straight row by row merge, but now that these lazy rows have appeared 
the field has changed a lot :-)

def typewriter(L,R):
     Z = [0] * len(R)
     M = [(L[0]+R[0],0)]
     while M:
         val,k = min(M)
         yield val
         Z[k] += 1
         M = []
         for k,x in enumerate(Z):
             if x < len(R):
                 M.append((L[k]+R[x],k))
             if not x:
                 break

A.