Hacker News Reader

Comment by pedrosorio | Hacker News Reader

> The dude invented merge sort and it's an effin' side-note to his work. Like, WAT.

Inventing merge sort is not a particularly impressive intellectual achievement.

It's trivial in an era where the concept of algorithms is established but less so back in the 1940s. You really had to be at the forefront to know that sorting algorithms are meaningful things to think about. But indeed mergesort is really not even a footnote of von Neuamnn's contributions to computing, which was perhaps not even 1/3 if his career. That's how much a giant he was.

Sorting was already a big thing in the punched card world.

Edit: adp with cards had been a thing for half a century by the time digital machines appeared. IBM was founded in 1911; NCR 1884.

The big advantage of electronic machines was speed. Early* digital computers didn't have much more memory than the card processors (64-128 bytes), but they weren't limited to cards/minute.

For 150 cards/min, see http://www.righto.com/2017/11/identifying-early-ibm-computer...

* EDIT: like ENIAC early. By MANIAC they already had ~5K of memory, which would've been unthinkable with the dieselpunk registers used by card machines: https://lh3.googleusercontent.com/-k0YcX-Qhvrw/WfxzfKNG1wI/A...

People have done merge sort, insertion sort, etc., by hand, for a very long time, probably centuries, and re-invented by many people. I would be very surprised if the steps had not been written down earlier. Algorithms done by hand, e.g. numerical methods, have been around for centuries too, so it's not that the concept was missing.

Especially because merging was how card machines sorted large decks

Reply on news.ycombinator.com