insertionSort(array x){ if(x.length < 2) end //we have 0 or 1 elements in the array for i = 1 to x.length-1, incrementing i = i+1 on each iteration temp = x[i] //pull out our element j = i-1 //start at the element next to our placehold and work forwards //shift the elements to the right until we find //a place to insert while j >= 0 AND x[j] > temp x[j+1] = x[j] j = j-1 end while x[j+1] = temp //insert our element end for }

We see that with an array, insertion sort does a lot of swapping of elements. However, with a Linked List, the swapping doesn't exist as Linked Lists are stored with relative positioning. So basically, we just have to insert the temp element back into the List at the appropriate index.

When we evaluate the Big-O of Insertion Sort, we get O(n^2). Our outer for loop takes linear time, iterating through n-1 elements. The inner loop also iterates through j elements worst case, which makes it linear n. So n*n --> O(n^2).