Insertion Sort

How it works

Insertion sort is a simple sorting algorithm that considers one element at a time in an array of data, and moves that item into its correct place, shifting all other elements along as it does so.

Consider the list above. It is an array of eight items, and we wish to sort it into ascending order.

Starting with the second item, we ask the simple question: is this value less than the previous value? If the answer is no, then no action is taken.

However, if the answer is yes, then we iterate (loop) through all of the values before that item, until we find the correct location for it. At this point, we shift the remaining items to the right one place, freeing up a gap into which to insert the value being moved.

The process then continues, until the end of the list is reached.

Look at the third row in the image.

Here, we are looking at element two (third item, in green). It less than 9 (the previous element) so it must move. We look at the two values that occur before it and see where it should be inserted. In this case, it is less than 7, the first value. So, the 7 and 9 are both moved to the right one space, freeing up element 0, into which the 6 is placed.

Pseudocode

sub InsertionSort(data)
  for i = 1 to len(data)
    if data[i]<data[i-1] then
      newPosition = 0
      //Find where to insert the value by checking
      //all values up to current position
      for j=0 to i
        if data[j]>data[i] then
          newPosition = j
          break
        end if
      end for
      //Store value that's moving in temp variable
      //Move all items from newPosition to i-1 along one place
      temp = data[i]
      for j = i to newPosition
        data[j+1] = data[j]
      end for
      data[newPosition] = temp
    end if
  end for
end sub
      

Advantages

This is a relatively simple algorithm to implement, and because it is not recursive, it is easy to step through in the event that something does not work well.

Disadvantages

The time complexity of this algorithm is O(n²) at its worst, the same as a bubble sort. So, as with the bubble sort, doubling the amount of data will result in the execution time quadrupling. Sorting 100x more data will take 10,000x longer.