🧠 Algorithms & Problem Solving, lesson 4 of 6
Sorting algorithms
Build bubble, insertion and merge sort, and see how they differ.
12 min
2 exercises
1 quiz
0/3 solved
Getting Python ready… examples can run in a moment.
Python's sorted() is excellent, so in real code just
use it. But writing sorts yourself is the classic
way to learn algorithmic thinking. Three famous ones:
- Bubble sort: swap neighbours that are out of order; big values "bubble" to the end
- Insertion sort: grow a sorted part on the left, inserting each new item in its place (like sorting cards in your hand)
- Merge sort: split in half, sort each half, then merge the sorted halves
Bubble sort
Each pass pushes the largest remaining value to the
end. The swapped flag stops early once a pass
changes nothing. Try an already sorted list.
What does this print? (It's one bubble sort pass.)
Insertion sort
The left part is always sorted. Insertion sort is very fast on lists that are almost sorted.
Selection sort
Implement selection sort: for each position
i, find the index of the smallest item from i to
the end, then swap it into position i. Return a new
sorted list (don't change the input, and don't use
sorted() or .sort()).
Merge sort uses divide and conquer. Its key step is merging two already-sorted lists: compare their front items, take the smaller, repeat. Split the list in half recursively until pieces have one item (which is always sorted), then merge back up.
Merge sort
Add a print(left, right) before the return in
merge_sort to watch the halves being merged.
Merge sorted lists
Write merge(a, b): both lists are already sorted;
return one sorted list containing every item from
both. Walk through them with two indexes, and don't
use sorted().