Algorithms · Lesson 2 of 6

Sorting

Bubble, merge and quick sort, plus stability and what Python really uses.

• Intermediate
• 18 min read
• 3 objectives

Before this lessonLesson 1: Searching

Sorting puts items in order, and a great deal of computing depends on it: fast searching, deduplication, merging, and ranking. Understanding a few classic algorithms teaches ideas (divide and conquer, invariants) that reach far beyond sorting itself.

Why sorting matters

Sorted data unlocks fast searching, easy duplicate detection, simple merging and readable reports. Sorting is also the classic place to study algorithm design, because there are many correct ways, with very different costs. In everyday Python you will simply call sorted(), but understanding how sorts work teaches you to think about efficiency.

Simple sorts: O(n squared)

Bubble sort repeatedly swaps adjacent items that are out of order, so large values "bubble" to the end. Insertion sort grows a sorted prefix by inserting each new item into place, like sorting playing cards in your hand. Both are easy to write, and insertion sort is genuinely fast on tiny or nearly sorted inputs.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

print(insertion_sort([5, 2, 4, 6, 1, 3]))

[1, 2, 3, 4, 5, 6]

Merge sort: O(n log n)

Merge sort is divide and conquer: split the list in half, sort each half recursively, then merge the two sorted halves by repeatedly taking the smaller front item. The list is halved log n times, and each level of merging does O(n) work, giving O(n log n) always, at the cost of O(n) extra memory.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 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:]

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

[3, 9, 10, 27, 38, 43, 82]

Quick sort

Pick a pivot, partition the items into smaller and larger, and recursively sort each side. Average time is O(n log n) and it sorts in place, which is why it is so popular. The worst case is O(n squared), for example when the pivot is always the smallest item; picking a random pivot makes that vanishingly unlikely.

import random

def quick_sort(a):
    if len(a) <= 1:
        return a
    pivot = random.choice(a)
    less    = [x for x in a if x < pivot]
    equal   = [x for x in a if x == pivot]
    greater = [x for x in a if x > pivot]
    return quick_sort(less) + equal + quick_sort(greater)

print(quick_sort([3, 6, 1, 8, 2, 9, 2]))

[1, 2, 2, 3, 6, 8, 9]

What you should actually use

In real code, call the built-in. Python's sorted() and list.sort() use Timsort, a hybrid of merge and insertion sort that is O(n log n) worst case and very fast on partially ordered data. Use key= to sort by a computed value and reverse=True for descending.

people = [("Ann", 31), ("Bob", 25), ("Cy", 31)]
print(sorted(people, key=lambda p: p[1]))
print(sorted(people, key=lambda p: (-p[1], p[0])))   # age desc, then name

[('Bob', 25), ('Ann', 31), ('Cy', 31)]
[('Ann', 31), ('Cy', 31), ('Bob', 25)]

Stability

A sort is stable if equal items keep their original relative order. In the first output above, Ann stays before Cy. Stability lets you sort by one field, then another, and keep the first ordering as a tiebreaker.

The lower bound

Any sort that works by comparing items needs at least about n log n comparisons in the worst case. Non-comparison sorts such as counting sort get O(n) only when values are small integers in a known range.

Bubble sort: the intuitive one

Repeatedly walk the list and swap neighbours that are out of order. Big values "bubble" to the end. It is simple but takes O(n^2) comparisons, so it is only for teaching.

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

print(bubble_sort([5, 2, 9, 1, 7]))

[1, 2, 5, 7, 9]

Merge sort: divide and conquer

Split the list in half, sort each half (recursively), then merge two sorted halves by repeatedly taking the smaller front item. It is O(n log n), dramatically faster on big inputs.

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

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

print(merge_sort([5, 2, 9, 1, 7, 3]))

[1, 2, 3, 5, 7, 9]

Sorting by more than one field

people = [("Ann", 31), ("Bob", 25), ("Cy", 31)]
by_age_then_name = sorted(people, key=lambda p: (-p[1], p[0]))
print(by_age_then_name)

[('Ann', 31), ('Cy', 31), ('Bob', 25)]

In real code, call sorted() or list.sort(). Python's built-in Timsort is stable, fast and already tuned. Reach for hand-written sorts only for learning or very special cases.

Key takeaways

• Simple sorts (bubble, insertion) are O(n^2); merge and quick sort are O(n log n).
• Merge sort divides, sorts halves recursively, then merges.
• Use built-in sorted with a key for real work; it is stable.

# Write your solution here