[Tutor] Merge Challenge

[Intatia]

Raymond Hettinger wrote:
> [Gregor]
> 
>>I'm very courious about your solution.
>>I tried
>>
>>c=a+b
>>c.sort()
>>
>>and that is indeed very fast. (Trying for half an
>>hour I couldn't find *any* faster one).
>>Will be hard to surpass.
> 
> 
> That's the winning solution.

So that's the best way to do it... *bangs head on desk*

> Tim Peter's amazing new sort routine discovers 
> the two sorted subsequences and merges them in
> a tight C coded loop at O(n) runtime.
> 
> For almost any other implementation of sort, the
> above solution would run at a much slower O(n log n)
> speed and would be beat by even badly coded pure
> python solutions running at O(n).
> 
> In case you can't tell, I'm very impressed with
> Tim's sort code.
> 
> 
> 
> Raymond Hettinger
> 
> 
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor
> 
>