Pointer Walk

Sorting Algorithms

Bubble, selection, insertion and merge sort put the same bars in order. Count the comparisons each one needs, and see why one of them pulls ahead as the list grows.

AlgorithmsBeginner12 min read

Why learn to sort?

You will almost never write your own sort. Every language has a good one built in. Sorting is still worth learning, for two reasons.

  • It is the clearest example of different ways to solve the same problem, with very different costs.
  • Sorted data makes other things fast. Binary search only works on sorted items.

This lesson puts four classic methods on the same ten bars and counts the comparisons each one makes.

Bubble sort

Rule: compare each pair of neighbours. If they are in the wrong order, swap them. Go through the list again and again until a pass makes no swaps.

On each pass the largest remaining value "bubbles" to the right end.

Bubble sortInteractive
7
3
9
1
6
10
2
8
4
5

Start. Compare neighbours and swap them if they are in the wrong order. Repeat until a pass makes no swaps.

Comparisons
0
Swaps
0
python
def bubble_sort(items):
    for end in range(len(items) - 1, 0, -1):
        swapped = False
        for i in range(end):
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        if not swapped:
            break                       # a clean pass: already sorted

It is the easiest to understand and one of the slowest. A value far from its place moves only one step per comparison.

Selection sort

Rule: scan the unsorted part for the smallest value. Move it to the front. Repeat with what is left.

Selection sortInteractive
7
3
9
1
6
10
2
8
4
5

Start. Find the smallest bar in the unsorted part and move it to the front. Repeat.

Comparisons
0
Swaps
0
python
def selection_sort(items):
    for start in range(len(items) - 1):
        smallest = start
        for i in range(start + 1, len(items)):
            if items[i] < items[smallest]:
                smallest = i
        items[start], items[smallest] = items[smallest], items[start]

It does very few swaps, at most one per pass. But it always scans the whole unsorted part, even when the list is already sorted. It never finishes early.

Insertion sort

Rule: take the next value and slide it left until it sits in its place among the values already sorted. This is how most people sort a hand of cards.

Insertion sortInteractive
7
3
9
1
6
10
2
8
4
5

Start. Take the next bar and slide it left into its place among the bars already sorted.

Comparisons
0
Swaps
0
python
def insertion_sort(items):
    for next_index in range(1, len(items)):
        i = next_index
        while i > 0 and items[i - 1] > items[i]:
            items[i - 1], items[i] = items[i], items[i - 1]
            i -= 1

A value that is already in place costs one comparison. So on a list that is nearly sorted, insertion sort is very fast: close to one comparison per item.

Merge sort

The first three share an idea: fix one value at a time. Merge sort does something different.

  1. Split the list in half

    Keep splitting until every piece holds one item. A list of one item is already sorted.

  2. Merge two sorted pieces into one sorted piece

    Look at the front item of each piece. Take the smaller one. Repeat.

  3. Keep merging

    Pieces of 1 become pieces of 2, then 4, then 8, until one sorted list remains.

Merge sortInteractive
7
3
9
1
6
10
2
8
4
5

Start. Split the list in half, sort each half, then merge the two sorted halves.

Comparisons
0
Items written
0

Merging is cheap because both pieces are already sorted. The smallest item overall must be at the front of one of them, so one comparison decides it.

python
def merge_sort(items):
    if len(items) <= 1:
        return items
    middle = len(items) // 2
    left = merge_sort(items[:middle])
    right = merge_sort(items[middle:])

    merged = []
    a = b = 0
    while a < len(left) and b < len(right):
        if left[a] <= right[b]:
            merged.append(left[a]); a += 1
        else:
            merged.append(right[b]); b += 1
    return merged + left[a:] + right[b:]

The scores

Same ten bars, four methods.

Comparisons to sort the same ten barsInteractive
39
Bubble sort
45
Selection sort
30
Insertion sort
23
Merge sort

Lower is better. With ten items the gap is modest. It grows quickly as the list gets longer.

On ten items the gap looks small: 45 for the worst, 23 for the best. The gap is not about ten items. It is about how the work grows.

  • The first three compare roughly every item with every other item. Double the list and the work goes up four times. This is O(n²).
  • Merge sort halves the list about log n times, and each level of merging touches every item once. Double the list and the work goes up a little more than two times. This is O(n log n).
ItemsAbout n² / 2 comparisonsAbout n log n comparisons
104533
1,000500,00010,000
1,000,000500,000,000,00020,000,000

At a million items the slow methods do 25,000 times more work. That is the difference between an instant and a long wait. See Big-O Notation and Logarithms.

Try them yourself

Bubble sortInteractive
Algorithm
7
3
9
1
6
10
2
8
4
5

Start. Compare neighbours and swap them if they are in the wrong order. Repeat until a pass makes no swaps.

Comparisons
0
Swaps
0

Side by side

Comparisons, typicalAlready sorted inputExtra memoryKeeps equal items in order
Bubblen²Fast, one passNoneYes
Selectionn²Still n²NoneNo
Insertionn²Fast, one passNoneYes
Mergen log nn log nA second copy of the listYes

"Keeps equal items in order" is called being stable. It matters when you sort by one thing and then another: sort people by name, then by city, and a stable sort leaves each city's people still in name order.

What real libraries use

  • Quicksort and its variants: O(n log n) on average, and sorts in place without a second copy.
  • Timsort, used by Python and Java for objects: merge sort that looks for runs that are already sorted, and uses insertion sort on small pieces.

So the simple methods are not useless. Insertion sort is the fastest choice for very short lists, and real sorts hand small pieces to it.

Key takeaways

  • Bubble, selection and insertion sort fix one value at a time and need about n² comparisons.
  • Merge sort splits the list, sorts the halves and merges them, and needs about n log n.
  • The difference is small on ten items and enormous on a million.
  • Insertion sort is very fast on short or nearly sorted lists, which is why real sorts still use it inside.
  • A stable sort keeps equal items in their original order.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    9 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress