HSC SDD - Planning and designing software solutions

An ascending insertion sort successively takes the next element to be sorted and places it in its correct position in the sorted part of the array.

To achieve this we need to logically divide the array into two parts – an unsorted part and a sorted part. Each pass through the unsorted part takes the end value of the unsorted part and places it in the correct position. It achieves this by successively moving the correct number of elements in the sorted part by one position to make room. Initially the sorted part contains one element. The size of the sorted part of the array increases by 1 with each pass.

Here is a video walkthrough of the logic

The following algorithm sorts an array of names into ascending order.

BEGIN InsertionSort
  Let First = 1
  Let Last = number of elements in the array
  Let PositionOfNext = Last – 1
  WHILE PositionOfNext >= First
    Let Next = Name (PositionOfNext)
    Let Current = PositionOfNext
    WHILE (Current < Last) AND (Next > Name (Current + 1))
      ’look for the position into which to insert the current name, and shuffle the sorted elements along until we find it.
      Increment Current
      Let Name (Current – 1) = Name (Current)
    ENDWHILE
    Let Name (Current) = Next
    ’put the current name to be sorted into its correct place
    Decrement PositionOfNext
    ’effectively shorten the length of the unsorted portion of the array
  ENDWHILE
END InsertionSort

Note: Variations of the algorithm are possible. In some versions, the task of finding the correct place to insert is separated from the task of moving the elements to make room. By doing this, the task of finding the correct place to insert can be done more quickly by using a binary search rather than a linear search.

If you need further information view http://courses.cs.vt.edu/csonline/Algorithms/Lessons/InsertionCardSort/index.html