the cedar ledge

# Insertion Sort

Date: December 19 2020

Summary:

Keywords: ##zettel #insertion #sorting #algorithms #archive

# Bibliography

Not Available

### Technical Definition

Insertion Sort: Efficient in-place sorting algorithm for a small input. Takes as an input an array A[1 . . n] containing a sequence of length n that is to be sorted. Upon algorithm termination, the input array A is sorted. [1]

### Plain-Word Explanation

Imagine playing a card game where each card in the game are numbers 1 - 10. I find it useful when playing card games to keep my cards in order from the smallest number on a card to the biggest number. I draw 6 cards and, in my hand, they are in the order of $[5, 2, 4, 6, 1, 3]$ - ugh! These are not in order!

I instantly set to organizing my hand by first switching $5$ and $2$. I then see that I can switch $4$ and $5$. I don't need to switch $6$ as it is bigger than $5$ - great! However, when I come to $1$, I know that $1$ is the smallest number in the game and I can instantly put it in the beginning and shift all the other cards in my hand. Finally, I come to $3$ - drat, this is a pain - I have to scan the previous cards in my hand before $3$ and see that it goes after $2$.

Hooray! I now have a sorted hand of $[1, 2, 3, 4, 5, 6]$ and am ready to win the game! What I just did here, is called insertion sorting!

### Code Implementation

function insertionsort(input)

@inbounds for curr = 2:length(input)
prior = curr - 1
while prior != 0
if input[curr] < input[prior]
input[curr], input[prior] = input[prior], input[curr]
end
curr = prior
prior -= 1
end
end
return input
end

## How To Cite

Zelko, Jacob. Insertion Sort. https://jacobzelko.com/12192020184137-insertion-sort. December 19 2020.

## References

[1] T. H. Cormen, Ed., Introduction to algorithms, 3rd ed. Cambridge, Mass: MIT Press, 2009.

## Discussion

CC BY-SA 4.0 Jacob Zelko. Last modified: January 17, 2023. Website built with Franklin.jl and the Julia programming language.