# Thread: who invented insertion sort?

1. ## who invented insertion sort?

Hello,
does someone know who the first person was, who had the idea to sort data the way we know it as "insertion sort" today? The idea seems to be from 1959 or earlier because shell sort is from then and seems to be based on it.

It's only a very simple algorithm but it's still hard to find the original developer. Or at least the person who first documented it in connection with data sorting for computers.

2. It might be hard to find the first person who came up with the idea behind insertion sort, because the simple version is one of the basic ways humans would sort a list of items.

Knuth (TAOCP 3, p. 82) writes that the variant of using binary insertion "was mentioned by John Mauchly as early as 1946, in the first published discussion of computer sorting."

3. Originally Posted by jibz
It might be hard to find the first person who came up with the idea behind insertion sort, because the simple version is one of the basic ways humans would sort a list of items.
Yes. Insertion sort is presumably prehistoric; accounting predates other writing.

Mechanical tabulating and sorting machines were used for automatically radix sorting punch cards circa 1900. (Or maybe it was only semi-automatic, with the machine sorting cards into bins depending on what holes they had, and the operator having to set up the next step to sort on the next column. I don't know.) If they didn't use insertion sort, it wouldn't have been because they didn't know the method, but because radix sorting fit the architecture better.

4. I think humans use Selection Sort and not Insertion Sort

5. Originally Posted by jibz
Knuth (TAOCP 3, p. 82) writes that the variant of using binary insertion "was mentioned by John Mauchly as early as 1946, in the first published discussion of computer sorting."
Well, if "binary" in this context means something like a binary searching procedure then insertion sort is not binary. It's actually linear.

Originally Posted by Paul W.
Mechanical tabulating and sorting machines were used for automatically radix sorting punch cards circa 1900.
Radix sort is based on counting sort. Not on insertion sort. But your assumption that radix sort fits the architecture better is probably correct because it's easier to build a machine that takes cards from a stack and throws it into 10 different output stacks instead of moving them back to top, lifting up some cards, inserting one in between then going down a little bit further, pull one out and insert it somewhere else in the middle of the stack ...

Originally Posted by Piotr Tarsa
I think humans use Selection Sort and not Insertion Sort
So the assumption that insertion sort has been used ever since isn't correct either. :-/

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•