3 ms·
Inside card sorters: 1920s data processing, relay logic and linear time sorting
- weinzierl 11y agoIf you also wondered about the "linear time sorting" part. Punch card sorters used an electro-mechanical (even without vacuum tubes) implementation of radix sort.
- Animats 11y agoCard 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.
- ntonozzi 11y agoAnother 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).
- GnarfGnarf 11y agoIf 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.
- FroshKiller 11y agoIf 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.
- raddad 11y ago>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 http://www.computerhistory.org/collections/catalog/102667304