[macosxnerd101]

The concept of Insertion Sort is very intuitive, probably more so than Selection Sort. Basically, we are given an array or List of some sort. We start at element 1 and essentially pull it out of the list. We then move all the elements before it down until we have a place to insert it. So let's go ahead and look at some pseudo-code:

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).

This post has been edited by macosxnerd101: 29 September 2011 - 08:33 AM

[mohaidriss]

Hi,

Your code is accurate, it helped me understand the insertion sort algorithm. However, a small mistake in your code is that the while's condition should be j >= 0 rather than j > 0.

I have manually checked and I detected it.

Thank you,
Mohamed