Inside card sorters: 1920s data processing, relay logic and linear time sorting

righto.com

44 points·kens··6 comments

Card sorters are not linear time. They're number of cards x number of columns of sort key. Sort keys, if unique, have to have size O(log N), so card sorters are O(N log N), as you'd expect.

You can beat O(N log N) with a radix-like sort (SyncSort, the first software patent, shows how), but you need more bins than a card sorter has.

Another way to look at it: Sorting is linear in the size of the input in bytes, but not item count. It's only comparison sort that happens to be O(n log n).

If you have 1,000 cards and you are sorting on 6 columns, you have to pass all the cards 6 times, which means reading 6,000 cards. Is this O(N log N)?

I know this because I did it for a living when I started working in 1970.

If you're interested in tabulators & punch cards and the impact they had on human history, read IBM and the Holocaust by Edwin Black. It's a sometimes dry but fascinating explication of the role IBM played in supporting the Holocaust and the strategies the company employed to continue doing business with Germany during the war.

>tabulators & punch cards and the impact they had on human history

I think everyone in school came home with a Christmas wreath made out of punch cards. Every now and then I still see cases of punch cards offered for free.

Here is an example of a wreath:

http://www.computerhistory.org/collections/catalog/102667304

If you also wondered about the "linear time sorting" part.

Punch card sorters used an electro-mechanical (even without vacuum tubes) implementation of radix sort.

Reply on news.ycombinator.com