Dmitry Kalashnikov

Basic Idea: You have a deck of unsorted cards. Lets start a sorted pile. So you take one card at a time from unsorted pile and appropriately place it in sorted pile. You keep doing it until you just left with a sorted pile.

OK, now lets break it down in high-level pseudo code. Lets assume we’re talking about arrays as a data structure.

Function InsertionSort (A):

n = number of elements in A

for i=1 to n-1:

for (j=i; j>0 && x[j-1] > x[j]; j–)

swap (x, j-1, j)

OK, that was some dense code :) It also happens to be one very bad-ass implementation of it. Lets break go through it and see whats going …

So, the outter loop:

walk from i=1 to n-1

is going to walk left to right and leave everything before i sorted, but everything it hasn’t touched yet unsorted. (you’ll see in a second why we’re starting with 1 instead of 0)

sorted pile

i

unsorted pile

The inner loop:

for (j=i; j>0 && x[j-1] > x[j]; j–)

swap (x, j-1, j)

is going to try to stick the new element into appropriate place in the “sorted” pile. The key thing to notice here is it walks right to left.

Now Visualize the inner loop:

• we have a sorted pile, with new element being at the very right of it.
• if the element to the left of it is bigger then our new element, we’ll swap them
• we’ll keep looking and seeing if the element to the left of us is smaller and swapping positions until there is nothing left.