Sorting Concepts

Sorting means rearranging elements into a defined order, usually ascending or descending. Listing numbers by size, names alphabetically, or orders by timestamp are all sorting. This chapter explains why sorting matters, the vocabulary used to compare sorting algorithms, and the everyday skill of sorting by a key.

Why sorting matters

Sometimes sorted output is the goal, but more often sorting is a preparation step that makes other work easy:

• Binary search: a sorted array lets you find a value in O(log n).
• Deduplication and grouping: equal values end up next to each other, so one pass is enough.
• Merging and comparing lists: two sorted lists can be merged with two pointers in one pass.
• Interval problems: sorted by start time, overlapping meetings and free slots appear in order.
• Rankings and top-k: leaderboards, search results and recommendations are all sorts by some criterion.

A useful habit when a problem looks hard: ask "would it be easier if the input were sorted?"

Comparison and non-comparison sorts

Most sorting algorithms only ask one question about two elements: "does a come before b?" These are comparison sorts, and they include bubble, insertion, selection, merge, quick and heap sort. Because they only compare, they work for anything with a defined order: numbers, strings, dates. It is proven that a comparison sort needs Ω(n log n) comparisons in the worst case (see the complexity chapter).

Counting sort and radix sort take a different route: they never compare elements and instead use the values themselves (integers, digits) as array indexes. With a small value range or a fixed number of digits they run in near-linear time, but they only apply to suitable data.

Vocabulary

Stability matters most when you sort by several criteria. Sort employees by name, then stable-sort by department, and within each department the names stay alphabetical.

staff = [("Mia", "ops"), ("Ava", "dev"), ("Leo", "ops"), ("Ben", "dev")]

by_name = sorted(staff, key=lambda s: s[0])
by_team = sorted(by_name, key=lambda s: s[1])  # stable: names stay sorted within a team
print(by_team)
# [('Ava', 'dev'), ('Ben', 'dev'), ('Leo', 'ops'), ('Mia', 'ops')]

Keys and comparators

In real code you rarely write a sorting algorithm. You tell the built-in sort what to sort by. Python's sorted() and list.sort() accept a key function, which is called exactly once per element; the results are then compared. A tuple key expresses several criteria at once.

orders = [
    {"id": 3, "price": 1200, "time": "10:05"},
    {"id": 1, "price": 800, "time": "09:40"},
    {"id": 2, "price": 1200, "time": "09:55"},
]

# price descending, then time ascending
ranked = sorted(orders, key=lambda o: (-o["price"], o["time"]))
print([o["id"] for o in ranked])  # [2, 3, 1]

words = ["banana", "apple", "Cherry"]
print(sorted(words))                    # ['Cherry', 'apple', 'banana'] (uppercase first)
print(sorted(words, key=str.casefold))  # ['apple', 'banana', 'Cherry'] case-insensitive
print(sorted(words, key=len, reverse=True))

Sometimes a function that compares two elements is more natural. C++ std::sort, Java's Comparator and JavaScript's Array.prototype.sort take comparators. In Python, functools.cmp_to_key turns a comparator into a key. A comparator returns a negative number (first goes before), zero (equal) or a positive number (first goes after), and it must answer consistently.

from functools import cmp_to_key

def by_version(a: str, b: str) -> int:
    pa = [int(x) for x in a.split(".")]
    pb = [int(x) for x in b.split(".")]
    return (pa > pb) - (pa < pb)

versions = ["1.10.0", "1.2.3", "1.2.10", "0.9"]
print(sorted(versions, key=cmp_to_key(by_version)))
# ['0.9', '1.2.3', '1.2.10', '1.10.0']

This particular case also works as key=lambda v: [int(x) for x in v.split(".")]. When a key function can express the order, prefer it: it is faster and harder to get wrong.

When to write your own

Production code almost always uses the standard library sort. It is well tested and tuned for realistic inputs such as nearly sorted data or many duplicates. Writing sorts yourself is still worthwhile: they contain the fundamentals of algorithm design (divide and conquer, invariants, recursion, worst-case analysis), and they come up constantly in coding interviews. Their parts also solve other problems: the merge step counts inversions, and the partition step finds the k-th smallest element.

Summary

• Sorting is most often a preparation step for searching, deduplication and interval processing.
• Comparison sorts are general but bounded below by Ω(n log n); counting and radix sort avoid the bound by exploiting the values.
• Stability, in-place behavior and adaptivity matter as much as time complexity.
• In practice, define the order with a key or comparator and let the built-in sort do the work.