Sorting — Putting Things in Order

What is it? #

Sorting arranges items by a rule. It matters far beyond tidy output: sorted data enables binary search, makes duplicates adjacent, and makes ranges easy to extract.

The simple algorithms — bubble, selection, insertion — compare neighbouring items and are O(n²). They are worth understanding once and then never writing again.

The practical algorithms — merge sort, quicksort, heapsort — are O(n log n). They work by dividing the problem rather than comparing every pair.

Python's built-in sort is Timsort, a hybrid that detects already-ordered runs and exploits them. On real data, which is often partly ordered, it is very hard to beat.

Think of it like this #

Sorting a deck of cards by hand, you probably pick up each card and slide it into the right place among the ones you are already holding. That is insertion sort, and it is fine for 52 cards.

Sorting a thousand exam papers, you would split the pile among several people, let each sort their pile, then merge the sorted piles. That is merge sort, and dividing the work is what makes it scale.

Simple example #

You need a list of orders sorted by date, and then by amount within the same date. You also want the ranking to be stable, so that orders with identical dates keep their original relative order.

Code #

orders = [
    {"id": "A", "date": "2026-09-21", "amount": 500},
    {"id": "B", "date": "2026-09-20", "amount": 900},
    {"id": "C", "date": "2026-09-21", "amount": 150},
]

# Use the built-in. It is Timsort: O(n log n) and stable.
by_date = sorted(orders, key=lambda o: o["date"])
by_date_then_amount = sorted(orders, key=lambda o: (o["date"], -o["amount"]))
print([o["id"] for o in by_date_then_amount])     # ['B', 'A', 'C']

# In-place, when you do not need the original order
orders.sort(key=lambda o: o["amount"], reverse=True)


# Merge sort — divide, sort each half, then merge
def merge_sort(items):
    if len(items) <= 1:                     # base case
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right)


def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:             # <= keeps it stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out


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


# Quicksort — pick a pivot, partition around it
def quick_sort(items):
    if len(items) <= 1:
        return items
    pivot = items[len(items) // 2]
    smaller = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]
    larger = [x for x in items if x > pivot]
    return quick_sort(smaller) + equal + quick_sort(larger)

                    average      worst        stable   notes
bubble sort         O(n^2)       O(n^2)       yes      teaching only
insertion sort      O(n^2)       O(n^2)       yes      good for tiny/nearly sorted
merge sort          O(n log n)   O(n log n)   yes      needs O(n) extra space
quicksort           O(n log n)   O(n^2)       no       fast in practice, in place
heapsort            O(n log n)   O(n log n)   no       no extra space
Timsort (Python)    O(n log n)   O(n log n)   yes      exploits existing order

How it works #

sorted(orders, key=...) is what you should reach for in real code. The key function computes the value to compare, and returning a tuple sorts by several fields.

Stability means equal items keep their original relative order. That is what lets you sort by amount and then by date and end up with both rules applied — a technique worth remembering.

merge_sort splits until each piece has one item, which is trivially sorted, then merges pairs back together. Merging two sorted lists is a single pass, and there are log n levels of merging, hence O(n log n). It needs extra space for the merged output, and the <= comparison is what keeps it stable.

quick_sort picks a pivot and partitions the rest into smaller and larger groups, then sorts those. On average it is fast and, implemented properly, sorts in place. Its worst case is O(n²) when the pivot is consistently poor — for example, always picking the first element of already-sorted data.

The version shown is written for clarity, not efficiency: the comprehensions make three passes and allocate new lists. A real implementation partitions in place.

Timsort, Python's built-in, finds runs of already-ordered elements and merges them. Real data frequently contains such runs, which is why it often beats textbook algorithms on real workloads.

Real-world use #

You will call sorted() constantly and implement sorting almost never. What matters is knowing the costs, and knowing that sorting is O(n log n) so you do not put a sort inside a loop.

Sorting enables other things: binary search needs it, deduplication is easier when duplicates are adjacent, and top-N problems are often solved by sorting — though a heap is better when N is small relative to the data.

Databases sort constantly for ORDER BY, for merge joins and for index building. A query that sorts a large result set without an index is often the slow part, and EXPLAIN will show it.

At very large scale, data does not fit in memory and external merge sort is used: sort chunks, write them to disk, then merge the sorted chunks. The same divide-and-merge idea, applied to files.

Common mistakes #

• Writing your own sort instead of using the built-in, which is faster and correct.
• Sorting inside a loop when sorting once before the loop would do.
• Assuming a sort is stable when it is not — it matters for multi-pass sorting.
• Sorting an entire dataset to find the top five. Use a heap.
• Using a key function that does expensive work; it is called once per element.

Practice #

Sort a list of employee dictionaries by department ascending and salary descending in a single call. Then implement insertion sort and merge sort yourself, run both on a shuffled list of 5,000 numbers, and time them against sorted().