Home  Back Topics CD Orders  INDEX 
Insertion Sort

Insertion Sort.

Example : Suppose we need to sort the list

21 12 32 17 19 25 26

The sort works by 'inserting' each number in the correct position.

It is easier to consider what happens in one pass of the insertion sort :

Suppose we are at the following position -

(three passes have already been done and the numbers 21,12, 32 and 17 have been 'inserted' in the list) :

12 17 21 32 19 25 26

The next number to be inserted is 19......remove it from the list and store in a temporary position....

19 12 17 21 32   25 26

Work back from the blank position. If the number is bigger than 19 then move it to the right..

19 12 17 21   32 25 26
19 12 17   21 32 25 26

and then insert number 19 into the blank position :

  12 17 19 21 32 25 26

The next number to be inserted is 25...and so on.

What would the list look like after the next pass?

 

Notes : The insertion sort is a fast sort - faster than the bubble sort for 'jumbled' files.

Pseudocode :

Assume the n records are held in an array Key[0..n], with Key[0] being used to hold the current key being looked at.

for counter = 2 to n  {start from second key}
  CurrentKey := key[counter];  
  key[[0] := CurrentKey;   {move key being looked at to position 0}
  ptr := counter - 1   {set pointer to the left of the blank position}
  while key[ptr] > CurrentKey do  
    move key[ptr] to key[ptr+1] {move key one position to the right}
    ptr := ptr - 1 {get ready to look at next key to the left}
  endwhile    
  key[ptr+1] := CurrentKey   {insert CurrentKey into blank position}
endfor