Insertion Sort

Test yourself on Insertion Sort with exam style questions, marked instantly.

Flashcards that come back just before you would forget them.

A revision plan that remembers what you know and shows what to do next.

See which topics you have nailed and which need another look.

Quiz yourself on Insertion SortGet your flashcardsBuild my revision planTrack my progress

Sorting Cards in Your Hand

Insertion sort is how most people sort playing cards. You pick up one card at a time and slide it into the right place among the cards you are already holding. The cards in your hand are always in order, and the pile still to pick up shrinks each time.

Insertion sort on the list 5, 3, 8, 1, 9, 2 in six rows. Start: 5 3 8 1 9 2, with 5 as the sorted part. Insert 3: 3 5 8 1 9 2. Insert 8: 3 5 8 1 9 2. Insert 1: 1 3 5 8 9 2. Insert 9: 1 3 5 8 9 2. Insert 2: 1 2 3 5 8 9. Sorted items are green and bold, and the item just inserted has a thick outline.

Insertion sort takes the next item and inserts it into its correct place in the sorted part on the left. The sorted part grows by one item each row. Insertion sort is named in the OCR J277 specification only. AQA and Edexcel name bubble sort and merge sort but not insertion sort.

Insertion Sort at a Glance

Feature Insertion Sort
Method Take the next item (the key) and insert it into its place in the sorted part
Sorted part Starts as the first item and grows by one each step
Shifting Larger items move one place right to make a gap for the key
Extra memory None: it sorts in place
Quickest on Short lists and lists that are nearly sorted
Compared with bubble sort Usually the better of the two, because it makes fewer moves

Deep Dive: Insertion Sort Trace

Sort [5, 2, 4, 1] into ascending order. The first item, 5, is the sorted part to begin with.

  • Key = 2: 5 is larger, so shift 5 right and insert 2. List: [2, 5, 4, 1]
  • Key = 4: 5 is larger, so shift 5 right. 2 is smaller, so stop and insert 4. List: [2, 4, 5, 1]
  • Key = 1: shift 5, 4 and 2 right, then insert 1 at the front. List: [1, 2, 4, 5]

A list of 4 items needs 3 steps, because the first item starts as the sorted part. A list of 6 items needs 5 steps.

Deep Dive: Best and Worst Lists

  • Already sorted, such as [1, 2, 3, 4]: every key is already in the right place, so nothing shifts. This is the quickest case.
  • Nearly sorted, such as [2, 3, 4, 1]: only the last key has to move, but it shifts three items.
  • Reverse order, such as [4, 3, 2, 1]: every key shifts past every item in the sorted part. This is the slowest case, with 6 shifts for 4 items.

Memory Trick

Insertion = cards in your hand. Pick the next card, slide the bigger cards along, and drop it into the gap.
The sorted part is always on the left and grows by one each step.

Exam Tips

  • Show the list after each step: circle or name the key each time.
  • Start correctly: the first item counts as the sorted part, so the first key is the second item.
  • Say when it is good: small lists and nearly sorted lists.
  • Common mistake: mixing it up with bubble sort. Insertion sort does not swap neighbours repeatedly, it inserts one key at a time.

Make this stick

Signing in gives access to all PrepWise features.

PrepWise is a trading name of A3M Quality Solutions Limited, registered in England and Wales, company number 14959172. Registered office: 202 Stroud Road, Gloucester, GL1 5LA. ICO registration ZC267069.