Sorting Algorithms - Insertion

Other algorithms: Bubble | Insertion | Selection | Merge | Quick

Description

With the insertion sort, lets say you have 4 items in order. You compare the new one to each existing item and insert it in the right place.

Detailed Instructions

1. Compare Box1 with Box2. Put the lightest one in the first space and the heaviest in the second space.
   
   
   
2. Compare Box3 with the lightest box.
   - If Box3 is lighter then insert it into the first place and push the others up. Move on to step 3.
   - Otherwise, if Box3 is heavier then put the lightest box back.
   - Compare Box3 with the second lightest box.
   - If Box3 is lighter then insert it into the second space and put the remaining box into the third space.
   - Otherwise, if Box3 is heavier then put the second box back and insert Box3 in the third space.
   
   
3. Compare Box4 with the lightest box.
   - If Box4 is lighter then insert it into the first place and push the others up. Move on to step 4.
   - Otherwise, if Box4 is heavier then put the lightest box back.
   - Compare Box4 with the second lightest box.
   - If Box4 is lighter then insert it into the second space and push the other boxes up. Move on to step 4.
   - Otherwise, if Box4 is heavier then put the second box back.
   - Compare Box4 with the third lightest box.
   - If Box4 is lighter then insert it into the third space and push the remaining box up.
   - Otherwise, if Box4 is heavier then put the third box back and insert Box4 in the fourth space.
   
   
4. By now you should hopefully be getting a feel for how to continue. The rule is:
   - Compare the new box with each of the existing boxes in order until you find the new one is lighter.
   - Then insert it and push the others up.
   
   
5. And finally, once you've completed the exercise, try to work out the maximum number of comparisons you would need to solve the problem with different numbers of boxes.