Sorting algorithms compared

TL;DR:

• Bubble sort swaps neighbours until nothing is out of order. It is simple but slow for large lists.

• Merge sort splits the list, sorts each half and merges. Quicksort picks a pivot and splits around it.

• Merge sort and quicksort are fast on average, O(n log n), while bubble sort is O(n²). In practice, you use your language's built-in sort.

Sorting is the most studied problem in computer science, partly because it is simple to state and partly because it has so many different solutions. We will sort the same list, [5, 2, 9, 1], three ways and trace each one, so you can see how the methods differ while ending in the same place.

The idea in plain words

All three algorithms take a list of numbers and return the same numbers in increasing order. They differ in strategy. Bubble sort repeatedly fixes neighbouring pairs. Merge sort divides the list, sorts each half, and combines the halves. Quicksort picks one item, the pivot, and puts smaller items on one side and larger on the other.

Worked example: sorting [5, 2, 9, 1] three ways

Bubble sort

Walk through the list comparing neighbours and swap them if they are out of order. After each pass the largest remaining item has bubbled to the end.

1. Pass 1: 5,2 swap gives 2,5,9,1. 5,9 fine. 9,1 swap gives 2,5,1,9.

2. Pass 2: 2,5 fine. 5,1 swap gives 2,1,5,9. (The last item is already placed.)

3. Pass 3: 2,1 swap gives 1,2,5,9. Done: four swaps in total.

def bubble_sort(a):
    a = list(a)
    for end in range(len(a) - 1, 0, -1):
        for i in range(end):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
    return a

Four swaps is no accident: the list has four inversions (pairs in the wrong order): (5,2), (5,1), (2,1) and (9,1), and each swap of neighbours removes exactly one.

Merge sort

Split [5, 2, 9, 1] into [5, 2] and [9, 1]. Split again into single items, which are already sorted. Merge pairs by repeatedly taking the smaller front item: [5] and [2] become [2, 5]; [9] and [1] become [1, 9]. Now merge [2, 5] with [1, 9]: compare 2 and 1, take 1; compare 2 and 9, take 2; compare 5 and 9, take 5; then take 9. The result is [1, 2, 5, 9].

def merge_sort(a):
    if len(a) <= 1:
        return list(a)
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    return out + left[i:] + right[j:]

Quicksort

Pick the last item as pivot. Pivot 1: nothing is smaller, so the left part is empty and the right part is [5, 2, 9]. Sort that with pivot 9: left is [5, 2], right empty. Sort [5, 2] with pivot 2: left empty, right [5]. Stitch it together: [], 1, then [] + [2] + [5], then 9, giving [1, 2, 5, 9].

def quick_sort(a):
    if len(a) <= 1:
        return list(a)
    pivot = a[-1]
    smaller = [x for x in a[:-1] if x <= pivot]
    larger = [x for x in a[:-1] if x > pivot]
    return quick_sort(smaller) + [pivot] + quick_sort(larger)

All three give [1, 2, 5, 9] for [5, 2, 9, 1]. For example, print(quick_sort([5, 2, 9, 1])) shows [1, 2, 5, 9].

Counting the work for four items

Bubble sort on four items compares 3 + 2 + 1 = 6 pairs, which is 4 × 3 ÷ 2. For ten items that becomes 10 × 9 ÷ 2 = 45, and for a hundred items it is 100 × 99 ÷ 2 = 4,950. The count grows with the square of the list length.

Merge sort splits four items into two levels of halving, since log₂ 4 = 2. At each level every item is looked at once during merging, so the work is roughly 4 × 2 = 8 item steps. For a hundred items there are about 7 levels, since 2⁷ = 128 is the next power of two above 100, so around 100 × 7 = 700 item steps, against 4,950 comparisons for bubble sort.

How they compare

In real programs you rarely write your own. A language's built-in sort, such as Python's sorted(), is carefully tuned and tested. Writing the algorithms yourself is for learning how they work, and for the cases that need something unusual.

When each one is the right choice

• Bubble sort: teaching, tiny lists, or when you must be able to explain every step. It is almost never the production choice.

• Merge sort: when you need steady performance and are willing to use extra memory, and when you sort data that does not all fit in memory at once, merging sorted pieces.

• Quicksort: when average speed matters and memory is tight, since good versions sort in place. Choose pivots carefully, for example the middle item or a random one, to avoid the bad case.

How to check your answer

• Same length and same items as the input? Sorting must not add or lose items.

• In order? Check each neighbouring pair.

• For bubble sort, count swaps and compare with the number of inversions.

• Test small cases: an empty list, one item, equal items, and an already-sorted list.

Common mistakes

• Forgetting the base case in merge sort and quicksort, which loops forever.

• Using < where <= is needed in the merge, which affects the order of equal items.

• Assuming quicksort is always fast. A sorted list with a last-item pivot is its worst case.

• Sorting a list in place when the caller still needs the original.

Where you will use it next

Merge sort and quicksort are both recursive, so you will want recursion explained with factorials. Sorted data is what makes binary search step by step possible.

Frequently asked questions

Which sort should I use in Python?

Use sorted() or list.sort(). Both are fast and correct, and you can sort by a key.

Why is bubble sort taught at all?

It is the simplest to understand, and it gives a baseline for comparing others.