Date: December 19 2020
Keywords: ##zettel #insertion #sorting #algorithms #archive
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. 
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 - ugh! These are not in order!
I instantly set to organizing my hand by first switching and . I then see that I can switch and . I don't need to switch as it is bigger than - great! However, when I come to , I know that 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 - drat, this is a pain - I have to scan the previous cards in my hand before and see that it goes after .
Hooray! I now have a sorted hand of and am ready to win the game! What I just did here, is called insertion sorting!
function insertionsort(input) 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
Zelko, Jacob. Insertion Sort. https://jacobzelko.com/12192020184137-insertion-sort. December 19 2020.
 T. H. Cormen, Ed., Introduction to algorithms, 3rd ed. Cambridge, Mass: MIT Press, 2009.