Computer Science
Insertion Sort

The insertion sort is the closest sort algorithm to the way that we might sort the array if we wrote the numbers on some cards. Imagine that this is the case. You would take the first card and place it on the table. You would then take the second card and place it to the left or right of the first one depending on whether it was greater or less than that item. When the third card is taken, if it goes at the start of the list, you would need to shuffle the other cards to the right to put it in the correct position.

The following algorithm can be used for an insertion sort,

For outerLoop = 1 To arrayLength - 1
   temp = item[outerLoop]
   innerLoop = outerLoop
   While (innerLoop > 0 And item[innerLoop - 1] >= temp)
      item[innerLoop] = item[innerLoop - 1]
      innerLoop = innerLoop - 1
   End While
   item[innerLoop] = temp
Next outerLoop

The AQA specification only lists Insertion Sort as an algorithm to learn. Cutting up pieces of paper and writing numbers on them is a good way to help you to understand how this sort works. You can also rewrite the algorithm so that the list is output after each iteration of the outerloop.

Make sure that you are aware of the many different approaches to sorting. Creating a program that compares the execution time (at different volumes) of each algorithm is a useful way to get a sense of how quickly they execute.

Insertion Sort In C#