An insertion sort involves processing a single value in each step. An order list is maintained throughout the sort process and a new element is added to that list each step. After each step, the inserted element will be in is correct place in the list. The following example shows how the insertion sort works:

The list "9,7,3,5,6" needs to be sorted from lowest to highest. The following steps are carried out:

• Step 1 - get first value from list (9)
• Step 2 - get second value from list (7) and compare to first value (9)
• If second value smaller than first value, place second value in front of first value (7,9)
• Step 3 - get third value from list (3) and compare to tail value (9) of current ordered list (7,9)
• If new element (3) smaller than tail value (9), place new element in front of tail value (7,3,9)
• If new element (3) smaller than first value (7), place new element in front of first value (3,7,9)
• Step 4 - get fourth value from list (5) and compare to each element in current ordered list (3,7,9) in a similar fashion to Step 3
• New ordered list is (3,5,7,9)
• Step 5 - get fifth value from list (6) and compare to each element in current ordered list (3,5,7,9) in a similar fashion to Step 3
• When 6 is compared to 5, 6 is placed in the list to create the final sorted list: 3,5,6,7,9

Note that in the last step, 6 does not need to be compared to 3. This is because it is known that any value before 5 will be less than 5 due to the previous steps being carried out.

Search for "Insertion Sort" on: Google | Kelkoo | Amazon | eBay (UK) | eBay (US)

Search for "Insertion Sort" on the rest of Computing Students: Insertion Sort