Results 1 to 5 of 5

Thread: who invented insertion sort?

  1. #1
    Member just a worm's Avatar
    Join Date
    Aug 2013
    Location
    planet "earth"
    Posts
    96
    Thanks
    29
    Thanked 6 Times in 5 Posts

    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. #2
    Member jibz's Avatar
    Join Date
    Jan 2015
    Location
    Denmark
    Posts
    114
    Thanks
    91
    Thanked 69 Times in 49 Posts
    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. #3
    Member
    Join Date
    Oct 2013
    Location
    Filling a much-needed gap in the literature
    Posts
    350
    Thanks
    177
    Thanked 49 Times in 35 Posts
    Quote Originally Posted by jibz View Post
    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. #4
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    I think humans use Selection Sort and not Insertion Sort

  5. #5
    Member just a worm's Avatar
    Join Date
    Aug 2013
    Location
    planet "earth"
    Posts
    96
    Thanks
    29
    Thanked 6 Times in 5 Posts
    Quote 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.


    Quote 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 ...


    Quote 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. :-/
    Last edited by just a worm; 16th March 2015 at 15:47.

Similar Threads

  1. Radix sort match finder
    By Conor in forum Data Compression
    Replies: 17
    Last Post: 13th February 2015, 14:19

Posting Permissions

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