Re: merging sorted sequences generically in Python

On Fri, Mar 23, 2012 at 06:58:39PM +0100, Dave Long wrote:
> >Merging sorted sequences was the fundamental data processing
> >framework of the COBOL era, and again of the MapReduce era.  But I
> >always found myself writing clumsy, special-case-filled merge code
> >for it.
> 
> 3/4 to 1/2 a century ago, you might have found yourself wiring clumsy,
> special-case-filled plugboards for it: cf
> http://ed-thelen.org/comp-hist/IBM077CollatorPrinciplesOfOperation-NeffR.pdf
> (with the resulting merge --at least ca. 1945-- running at the amazing rate
> of 8 records/second!)

Wow!  If I had 8000 punched cards, a binary merge sort would take 13 passes, or
about a second and a half per card.  Sorting them by hand would probably be
faster, although the manual suggests doing this incrementally as they arrive.

I'd think that the old inverted radix sort (first partition by last digit, then
next-to-last-digit, etc.) would be faster.

Kragen
-- 
To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss