Insertion Sort

Part1: How Insertion Sort Works

Classic simple easy to understand but not very efficient for large sets. Let’s see what’s going on :

Given an array of unsorted values we can start at the first entry left of the key, (the key is the second element in the array to start), and compare that value with the key . If the value is out of order compared to the key  and is not the left most element overwrite the element to its right  (think of the list existing in a row in front of you) move to the left comparing to the key again.   Once the correct ordering is achieved the key is inserted to previously “moved” location. If you cannot move to left you are in the first position write the key here as it is the smallest element now.

Look at my horrible graphic (to match the description) and be amazed.

Maybe this video does it better.

7 little lines of pseudocode:

for j=2 to A.length
   i = j - 1
   key = A[j]
   while i > 0 and A[i] > key 
       A[i + 1] = A[i]
       i = i - 1
   A[i + 1] = key