3 ms·
Mergesort with punched card decks would have been fairly obvious, so I wouldn't be surprised if the general idea predated his software implementation by at leas
by 082349872349872 4y ago
Mergesort with punched card decks would have been fairly obvious, so I wouldn't be surprised if the general idea predated his software implementation by at least several decades?
- bee_rider 4y agoI’m not sure I see the connection to punched card decks, other than that they are a thing that might need to be sorted… but then, people have been sorting things by hand for all of history. He and his colleague are credited with the design of the algorithm… suppose it is possible they drew general inspiration from how people might sort something by hand.
- SamReidHughes 4y agoPunched cards were generally processed by machines in a streaming fashion.
- wolfram74 4y agoBut if you dropped them, you'd need to put them back in order, and decks are very amenable to splitting and dealing.
- marcosdumay 4y agoIt's a very numerous thing that needs to be sorted often, and composed of items with similar shapes. That combination isn't very common. But I wouldn't be surprised if somebody invented it 2 or 3 millennia ago either.
- bee_rider 4y agoI think they were actually talking about the data access pattern, with mergeSort you get nice sequential access to the arrays of course. I don’t actually know how data was fed into card based systems, I mean I know they fed the cards in, but I assumed the bulk data was read from tapes or something and cards mostly held the programs. Maybe not though, it is all quite a bit before my time!
- MichaelMoser123 4y agocould a tabulating machine do recursion? Did it have a stack?
- eru 4y agoYou can implement a bottom-up merge sort iteratively fairly easily. It's basically two nested loops only.
- halpmeh 4y agoIsn’t radix sort way better for punched cards (and more obvious)?
- eru 4y agoDepends what your sort key is. Radix sort works only for small-ish integers, but not well eg for names that you want to sort alphabetically. Nor for floating point numbers or even large integers.
- bee_rider 4y agoCut the cards to correspond to their magnitude and you can just use spaghetti sort.