Sorting algorithms

Algorithms & Problem Solving, lesson 4 of 6

🧠 Algorithms & Problem Solving, lesson 4 of 6

Sorting algorithms

Build bubble, insertion, selection 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. Four 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)
  • Selection sort: find the smallest remaining item and swap it to the front (you'll write this one)
  • Merge sort: split in half, sort each half, then merge the sorted halves
Example

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.

Walkthrough

bubble_sort([5, 1, 4, 2, 8])

1542801234
Step 1 of 10
pass = 1
swapped = True

Pass 1 compares neighbours left to right. 5 > 1, so they swap.

compared
in its final place
Quiz

What does this print? (It's one bubble sort pass.)

Example

Insertion sort

The left part is always sorted. Insertion sort is very fast on lists that are almost sorted.

Walkthrough

insertion_sort([7, 3, 5, 1])

73510123i
Step 1 of 4
current = 3

A single item is already sorted, so start at i = 1 with current = 3.

sorted part
current
Walkthrough

Selection sort on [29, 10, 14, 37, 13]

291014371301234ismallest
Step 1 of 7

i = 0: scan everything from index 0 on. The smallest is 10, at index 1.

scanned for the smallest
smallest found
final place
Exercise

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.

Walkthrough

merge([1, 4, 9], [2, 3, 10])

left149012iright2310012jresult10
Step 1 of 6

Both lists are sorted, so the smallest item overall is one of the two fronts. 1 ≤ 2: take 1, i moves on.

taken this step
already taken
merged
Example

Merge sort

Add a print(left, right) before the return in merge_sort to watch the halves being merged.

Walkthrough

merge_sort([38, 27, 43, 3, 9, 82, 10])

3827433982100123456
Step 1 of 7

7 items, so mid = 7 // 2 = 3.

a piece
the piece next to it
sorted

Drawn level by level. The code finishes the whole left half before it starts the right half, but it builds exactly these pieces.

Exercise

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().