Sorting Algorithms

Bubble sort

Repeatedly compare adjacent pairs and swap if out of order. Each full pass "bubbles" the next largest value to the end.

Pass 1 on [5,3,8,1]:
3,5,8,1 → 3,5,8,1 → 3,5,1,8   (8 now at the end)

• Simple but slow; up to n² comparisons.

Insertion sort

Build a sorted section one item at a time, inserting each new card into its correct place (like sorting a hand of cards).

• Efficient for small or nearly-sorted lists.

Merge sort

Divide and conquer:

1. Split the list in half repeatedly until each part has 1 item
2. Merge pairs back together in order

• Fast on large lists (n log n) but uses more memory.

Comparison

Algorithm	Speed	Memory	Best for
Bubble	Slow	Low	Teaching / tiny lists
Insertion	Medium	Low	Small / nearly sorted
Merge	Fast	Higher	Large lists

Exam tip

Be ready to show each pass of bubble sort — write the whole list after every full pass, and remember merge sort's strength is speed on large data.