beginnerintermediateadvanced

Data Structures & Algorithms · Section 9

Sorting Algorithms

Level: beginner
Read: 90 min
Concepts: 15

The classic sorting algorithms — bubble, selection, and insertion sort as the O(n²) baseline, merge sort and quicksort as the O(n log n) workhorses, counting and bucket sort for when the input has special structure, and stability and pivot choice as the details that decide whether they actually work — plus the Python tools (sorted(), key=, cmp_to_key) that replace hand-rolling any of them in real code.

What is true here

Merge sort is O(n log n) unconditionally at the cost of O(n) extra space; quicksort is in-place but risks O(n²) on a badly chosen pivot.
Stability means two elements tied on the sort key keep their original relative order — Python's sorted()/.sort() guarantee it.
key=fn computes a comparison value once per element, not once per comparison, which is what keeps sorting O(n log n) even with a custom key.
sorted() returns a new list and leaves the original alone; .sort() mutates in place and returns None — the source of the most common sorting bug in Python.

What you will be able to do

Explain how merge sort and quicksort work, and when each one's worst case is actually reached
Choose a sorting algorithm based on data size, memory constraints, and how nearly-sorted the input already is
Sort by a computed key, by multiple criteria, and in reverse, using the standard-library tools instead of hand-rolled comparators
Explain what sort stability means and when it actually changes the output

Concepts

How each classic sort works and its complexity, from the O(n²) teaching sorts through merge sort and quicksort to the non-comparison sorts.

Bubble sort — O(n²), teaching-only

referencebeginner

Bubble sort repeatedly walks the array, swapping any adjacent out-of-order pair — each full pass "bubbles" the largest remaining unsorted value to its correct position at the end.

What we're doing: Sort a list by repeatedly bubbling the largest remaining value to the end, stopping early once a full pass makes no swaps.

bubble_sort.pypython

def bubble_sort(arr):
    arr = arr.copy()
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr


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

6: The inner loop shrinks by one each pass — the last i elements are already in their final position and never need rechecking.
9: A pass with no swaps means the array is already sorted — stopping early is what keeps the best case O(n) instead of always O(n²).

Output

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

Why this works: Each pass moves the largest unsorted value one step closer to its final spot at the end — after enough passes, every value has bubbled to its correct position.

Remember: Bubble sort is O(n²) and exists to teach the idea of repeated adjacent swaps — insertion sort covers the same practical niche with less real work.

Selection sort — O(n²), teaching-only

referencebeginner

Selection sort repeatedly scans the unsorted remainder for its smallest value and swaps it into place at the front — one swap per pass, unlike bubble sort's many.

What we're doing: Sort a list by repeatedly finding the minimum of the unsorted remainder and swapping it to the front.

selection_sort.pypython

def selection_sort(arr):
    arr = arr.copy()
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr


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

5: min_index tracks the smallest value found so far in the UNSORTED remainder, starting at position i.
9: Exactly one swap per outer-loop iteration — the found minimum moves directly into position i.

Output

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

Why this works: Each outer iteration places the correct value at position i by scanning everything after it for the true minimum — after n iterations, every position holds its final value.

Remember: Selection sort always does O(n²) work, with no early exit, but only n - 1 total swaps — the right trade when writes cost far more than comparisons.

Insertion sort — good for nearly-sorted/small input

standardbeginner

Insertion sort builds up a sorted prefix one element at a time, shifting each new value backward past every already-sorted value bigger than it — exactly how most people sort a hand of playing cards.

Think of it as

Everything before index i is already sorted. Take arr[i], and shift it backward past every element bigger than it, one swap-like move at a time, until it lands next to something smaller (or reaches the front). The sorted prefix has now grown by one, and the process repeats for i + 1.

What we're doing: Sort a list by inserting each element backward into the already-sorted prefix before it.

insertion_sort.pypython

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


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

4: key is the value being inserted — everything before index i is already sorted from previous iterations.
6: Each larger element shifts one slot right, making room; the loop stops the moment something smaller (or the start) is reached.

Output

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

Why this works: Each key is walked backward past every larger value already placed, landing in its correct spot — by the time i reaches the end, the whole array has been built up as a sorted prefix, one insertion at a time.

Remember: Insertion sort is O(n²) worst case but close to O(n) on nearly-sorted input, since the inner loop only runs as far as something actually needs to move.

Merge sort — O(n log n), stable, extra space

corebeginner

Merge sort splits the array in half, recursively sorts each half, then merges the two now-sorted halves back together — the same two-pointer merge from Two Pointers, applied recursively.

Think of it as

Splitting in half recurses log₂(n) levels deep before hitting single-element (already "sorted") pieces. Merging two sorted halves back together costs O(n) at each level, and there are log₂(n) levels — O(n) work times O(log n) levels gives O(n log n) total.

What we're doing: Sort a list by recursively splitting in half and merging the sorted halves back together.

merge_sort.pypython

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


def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result


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

4: A single element (len <= 1) is trivially "sorted" — this is the base case that stops the recursion.
5: Both halves are sorted independently and recursively before merge ever runs — merge only ever combines two ALREADY-sorted sequences.

Output

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

Why this works: [5, 2, 4, 6, 1, 3] splits into [5, 2, 4] and [6, 1, 3], each recursively sorted to [2, 4, 5] and [1, 3, 6], then merged by repeatedly taking the smaller front — producing the fully sorted result.

Using < instead of <= in the merge comparison, breaking stability

Wrong

python

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


left = [(1, "a"), (2, "b")]
right = [(2, "c"), (3, "d")]
print(merge_unstable(left, right))

Better

python

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

What you see: merge_unstable puts (2, "c") from the right half before (2, "b") from the left half — [(1, "a"), (2, "c"), (2, "b"), (3, "d")] — even though (2, "b") appeared earlier in the original data.

Why: With a strict <, a tie (left[i][0] == right[j][0]) always falls to the else branch and takes from the RIGHT side first. Since the left half represents earlier original positions, that silently reverses the relative order of equal-key elements. <= instead takes from the left on a tie, preserving it.

Merge Sorted ArrayeasyLeetCode
The merge half of this pattern in isolation — worth solving before tackling the full recursive sort.
Sort an ArraymediumLeetCode
Implement merge sort (or another O(n log n) sort) from scratch — the canonical exercise for this exact algorithm.

Remember: Merge sort is O(n log n) unconditionally, at the cost of O(n) extra space — and its comparison must use <=, not <, to actually keep the stability the algorithm is known for.

Was this helpful?

Quicksort — O(n log n) average, O(n²) worst case, in-place

corebeginner

Quicksort picks a pivot, partitions the array so everything smaller ends up on its left and everything bigger on its right, then recursively sorts each side — the pivot itself never needs to move again.

Think of it as

Once partitioning finishes, the pivot sits at its FINAL sorted position — everything before it really is smaller, everything after really is bigger. Recursively repeating this on each side is enough to sort the whole array, since every element eventually becomes a pivot exactly once.

What we're doing: Sort a list by partitioning around a randomly chosen pivot and recursively sorting each side.

quicksort.pypython

import random


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


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

6: A RANDOM pivot makes a worst-case-triggering input astronomically unlikely — see the mistake below for what a fixed pivot risks.
8: equal is its own bucket, separate from less/greater — needed so a pivot value never gets compared against itself or re-sorted.

Output

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

Why this works: Regardless of which value the random pivot happens to be, less/equal/greater always partition correctly around it — the final concatenation is always sorted, only the RECURSION SHAPE (and therefore speed) depends on which pivot got picked.

Always picking a fixed position (e.g. the last element) as the pivot

Wrong

python

max_depth_fixed = 0


def quicksort_fixed_pivot(arr, depth=0):
    global max_depth_fixed
    max_depth_fixed = max(max_depth_fixed, depth)
    if len(arr) <= 1:
        return arr
    pivot = arr[-1]
    less = [x for x in arr[:-1] if x <= pivot]
    greater = [x for x in arr[:-1] if x > pivot]
    return quicksort_fixed_pivot(less, depth + 1) + [pivot] + quicksort_fixed_pivot(greater, depth + 1)


quicksort_fixed_pivot(list(range(20)))
print("fixed pivot on sorted input, max depth:", max_depth_fixed)

Better

python

import random

random.seed(42)
max_depth_random = 0


def quicksort_random_pivot(arr, depth=0):
    global max_depth_random
    max_depth_random = max(max_depth_random, depth)
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return quicksort_random_pivot(less, depth + 1) + equal + quicksort_random_pivot(greater, depth + 1)


quicksort_random_pivot(list(range(20)))
print("random pivot on sorted input, max depth:", max_depth_random)

What you see: On an already-sorted 20-element list, always pivoting on the last element reaches recursion depth 19 (essentially one level per element); a random pivot on the exact same input reaches depth 7.

Why: On sorted input, the last element is always the current maximum, so "greater" is always empty and "less" shrinks by only one element per call — degenerating into a linear chain instead of a balanced split. A random pivot has no reason to consistently pick an extreme value, so the split stays roughly balanced.

Sort Array By ParityeasyLeetCode
A single partition step in isolation — evens to one side, odds to the other, the same shape as one quicksort partition without the recursion.
Kth Largest Element in an ArraymediumLeetCode
Quickselect — the same partition idea, but only recursing into the ONE side that contains the answer, averaging O(n) instead of O(n log n).

Remember: Quicksort's O(n log n) average case depends entirely on the pivot roughly halving the array — a pivot chosen from a fixed position is exactly what an adversarial (or already-sorted) input can exploit to force O(n²).

Partition scheme (Lomuto vs Hoare, conceptually)

standardbeginner

Both partition schemes rearrange an array section in place so everything less than a pivot ends up before everything greater — Lomuto tracks one boundary while scanning left to right; Hoare closes two pointers in from both ends.

Think of it as

Lomuto: walk left to right with a single index i marking the boundary of 'everything confirmed smaller than the pivot so far'; every time a smaller value is found, swap it just past that boundary and advance it. Hoare: start pointers at both ends and swap across them whenever the left one finds something too big and the right one finds something too small, stopping once they cross.

What we're doing: Partition an array around its last element using Lomuto's scheme, in place.

lomuto_partition.pypython

def lomuto_partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


nums = [5, 2, 4, 6, 1, 3]
pivot_index = lomuto_partition(nums, 0, len(nums) - 1)
print(pivot_index, nums)

3: i starts one before low — it only ever advances when a value belongs in the "smaller than pivot" region.
7: The final swap puts the pivot (arr[high]) directly after everything confirmed smaller — its correct final resting place.

Output

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

Why this works: The pivot (3) lands at index 2, with 2 and 1 (both <= 3) before it, and 6, 5, 4 (all > 3) after it — the array is partitioned around the pivot, though neither side is fully sorted yet.

Remember: Both schemes partition in O(n) — Lomuto is simpler to write and returns the pivot's exact final index; Hoare does fewer swaps but its returned index is only a split point, not the pivot's position.

Counting sort — O(n + k), when values are bounded integers

standardbeginner

Counting sort counts how many times each value appears, then reads the counts back out in value order — no comparisons between elements at all, so it can beat any comparison-based sort when values are bounded integers.

Think of it as

Build an array indexed by VALUE, not position — counts[5] holds how many times the value 5 appeared in the input. One pass over the input fills it in; one pass over the counts array, writing each value out as many times as it was counted, produces the sorted result.

What we're doing: Sort a list of small integers by counting occurrences of each value.

counting_sort.pypython

def counting_sort(arr, max_value):
    counts = [0] * (max_value + 1)
    for x in arr:
        counts[x] += 1
    result = []
    for value, count in enumerate(counts):
        result.extend([value] * count)
    return result


print(counting_sort([4, 2, 2, 8, 3, 3, 1], 8))

3: One pass over the input — each value increments its own slot in counts, with no comparisons to any other element.
7: Reading counts in index order automatically yields ascending order — value 1 is emitted before value 2, and so on.

Output

[1, 2, 2, 3, 3, 4, 8]

Why this works: counts ends up as [0, 1, 2, 2, 1, 0, 0, 0, 1] for values 0 through 8 — reading it back out (skipping zero-count values, repeating others) reconstructs the sorted list directly.

Height CheckereasyLeetCode
Counting sort the heights (bounded 1-100), then compare the result position-by-position to the original array.
Sort ColorsmediumLeetCode
Only 3 possible values (0, 1, 2) — a textbook case for counting sort, though the one-pass Dutch-flag partition is the expected in-place solution.

Remember: Counting sort trades comparisons for counting — O(n + k) instead of O(n log n) — but only pays off when the value range k is small relative to n.

Bucket sort — for uniformly distributed input

referencebeginner

Bucket sort scatters values into several buckets based on their approximate range, sorts each small bucket individually, then concatenates the buckets in order — fast specifically when values are spread evenly across the range.

What we're doing: Sort floating-point values in [0, 1) by scattering them into buckets based on their magnitude.

bucket_sort.pypython

def bucket_sort(arr, bucket_count=5):
    buckets = [[] for _ in range(bucket_count)]
    for x in arr:
        index = min(int(x * bucket_count), bucket_count - 1)
        buckets[index].append(x)
    result = []
    for bucket in buckets:
        result.extend(sorted(bucket))
    return result


print(bucket_sort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12]))

4: x * bucket_count scales [0, 1) up to [0, bucket_count) — its integer part picks which bucket a value falls into.
8: Concatenating buckets in order works because bucket 0 holds only smaller values than bucket 1, and so on — only WITHIN a bucket does anything need actual sorting.

Output

[0.12, 0.17, 0.21, 0.26, 0.39, 0.72, 0.78, 0.94]

Why this works: Values scatter across 5 buckets by magnitude (0.12/0.17/0.21/0.26 in the lowest, 0.94 in the highest); sorting each small bucket and concatenating in bucket order reconstructs the full sorted list.

Remember: Bucket sort pays off specifically when values are uniformly spread across a known range — clustered input defeats the whole point, since one bucket ends up doing all the work.

Stability of a sort, and when it matters

standardbeginner

A stable sort never reorders two elements that compare equal on the sort key — sort by score alone, and everyone tied on score keeps whatever relative order they already had. An unstable sort makes no such promise.

Think of it as

Picture sorting a list of exam results by score, where several students tied at 90. Stability asks: among just those tied students, does the sort disturb the order they were already in? A stable sort answers no, always — which is exactly what lets you sort by a SECONDARY key first, then a primary key, and have the secondary order survive as the tie-breaker.

What we're doing: Confirm that sorting by score alone keeps students tied on score in their original relative order.

stability.pypython

students = [("Alice", 90), ("Bob", 85), ("Cara", 90), ("Dee", 85)]
by_score = sorted(students, key=lambda s: s[1], reverse=True)
print(by_score)

2: The sort key is ONLY the score — name plays no role in the comparison at all.

Output

[('Alice', 90), ('Cara', 90), ('Bob', 85), ('Dee', 85)]

Why this works: Alice and Cara are tied at 90; Alice appeared first in the original list and stays first after sorting. The same holds for Bob before Dee at 85 — stability preserved both ties exactly as they started.

Remember: Stability only shows up when two elements tie on the sort key — a stable sort guarantees their original relative order survives, which is what makes sorting by multiple keys reliable.

Was this helpful?

Choosing a sort based on data size, memory constraints, and nearly-sorted-ness

referencebeginner

In real code, reach for the built-in sorted()/.sort() by default — it already picks good behavior for you. Hand-write a specific algorithm only when a specific constraint (bounded integers, near-sorted input, hard memory limits) makes a difference.

Remember: Default to the built-in sort; reach for a specific algorithm only when a concrete constraint (bounded values, near-sorted input, or a hard memory ceiling) actually calls for it.

Was this helpful?

Python tools

The standard-library sorting interface that replaces hand-writing any of the above in real code.

`sorted()` and `list.sort()` — Timsort, stable, O(n log n)

corebeginner

sorted(iterable) builds and returns a brand-new sorted list, leaving the original untouched. list.sort() sorts a list in place and returns None. Mixing up which one returns what is the single most common sorting bug in Python.

Think of it as

Ask: do I need a NEW sorted list while keeping the original as-is (sorted()), or do I want to permanently rearrange a list I already have (.sort())? .sort() only exists on list objects and always returns None, exactly like a function whose whole job is a side effect — there is nothing useful to assign its result to.

What we're doing: Compare sorted() (returns a new list) against list.sort() (mutates in place, returns nothing).

sorted_vs_sort.pypython

nums = [3, 1, 2]
new_list = sorted(nums)
print(nums, new_list)

nums.sort()
print(nums)

2: sorted(nums) returns a NEW list — nums itself is completely unaffected by this line.
5: nums.sort() mutates nums directly — there is no return value worth capturing.

Output

[3, 1, 2] [1, 2, 3]

Why this works: After sorted(nums), nums is still [3, 1, 2] — completely untouched — while new_list holds the sorted result [1, 2, 3]. Only after calling nums.sort() does nums itself become sorted (this call's print isn't shown above, but the third line of output would read [1, 2, 3]).

Assigning the result of .sort() back to the variable

Wrong

python

nums = [3, 1, 2]
nums = nums.sort()
print(nums)

Better

python

nums = [3, 1, 2]
nums.sort()
print(nums)

What you see: nums = nums.sort() makes nums print as None — the list itself, now sorted, is thrown away because .sort() has no return value to assign.

Why: .sort() sorts nums in place and returns None, like every in-place list mutator. Assigning that None back onto nums overwrites the very list that was just correctly sorted.

Squares of a Sorted ArrayeasyLeetCode
sorted(x * x for x in nums) solves it directly in one line — the O(n) two-pointer solution is the intended follow-up once that works.
Merge IntervalsmediumLeetCode
sorted(intervals, key=lambda x: x[0]) is the first line of almost every interval problem — sort by start, then sweep.

Remember: sorted() returns a new list and leaves the original alone; .sort() mutates in place and returns None — never write nums = nums.sort().

`key=` parameter instead of writing custom comparators

standardbeginner

key=fn tells sorted()/list.sort() to compare elements by fn(element) instead of the elements themselves — fn runs once per element, not once per pair compared.

Think of it as

Instead of writing a function that answers 'which of these two comes first?' for every pair being compared, key=fn answers a simpler question once per element: 'what value should represent this for sorting purposes?' Python computes fn(element) for every element up front, then compares those computed values directly — which is exactly why key= stays O(n log n) instead of paying fn's cost on every comparison.

What we're doing: Sort strings by length instead of alphabetically.

key_parameter.pypython

words = ["banana", "kiwi", "apple", "fig"]
print(sorted(words, key=len))

2: key=len means "compare len(word) for each word", not the words themselves — len is just an ordinary function passed by name.

Output

['fig', 'kiwi', 'apple', 'banana']

Why this works: The lengths are fig=3, kiwi=4, apple=5, banana=6 — sorting by those computed lengths, not by alphabetical order, produces this exact ordering.

Remember: key=fn computes a comparison value once per element, up front — pass a function by name (len, str.lower) or a lambda for anything more specific.

Sorting by multiple criteria (`key=lambda x: (x[0], -x[1])`)

standardbeginner

A tuple key sorts by its first element as the primary criterion, using the second (and further) elements only to break ties — exactly like a multi-column ORDER BY in a database query.

Think of it as

Python compares tuples element by element: the first elements decide the order unless they are EQUAL, in which case the second elements decide, and so on. key=lambda x: (x[0], -x[1]) uses that directly — sort by x[0] first, and only among ties on x[0], sort by x[1] (negated, for descending on that field alone).

What we're doing: Sort records by name ascending, then by count descending within each name.

multi_criteria.pypython

records = [("apple", 3), ("banana", 1), ("apple", 1), ("banana", 2)]
print(sorted(records, key=lambda r: (r[0], -r[1])))

2: r[0] (the name) is the primary key; -r[1] only matters for breaking a tie on the name.

Output

[('apple', 3), ('apple', 1), ('banana', 2), ('banana', 1)]

Why this works: Both "apple" records come before both "banana" records (primary key, ascending). Within "apple", 3 comes before 1 because -3 < -1 sorts first (descending on the count); the same holds for "banana"'s 2 before 1.

Sort the PeopleeasyLeetCode
sorted(zip(heights, names), key=lambda x: -x[0]) pairs and sorts by height descending in one line.
Meeting Rooms IImediumLeetCode
Sorting intervals by (start, end) as a tuple key is the standard first step before sweeping through them.

Remember: A tuple key sorts left-to-right, tie-by-tie — negate a numeric field to flip only that ONE field to descending while the rest stay ascending.

Was this helpful?

`reverse=True` vs negating the sort key

referencebeginner

reverse=True flips the FINAL sorted order after normal ascending comparison; negating a numeric key value flips what counts as "smaller" before comparing — they agree for plain numbers, but only negation lets one field of a multi-key tuple go descending while the rest stay ascending.

What we're doing: Compare reverse=True against key negation for numbers, then see negation fail on strings.

reverse_vs_negate.pypython

nums = [3, 1, 4, 1, 5]
print(sorted(nums, reverse=True))
print(sorted(nums, key=lambda x: -x))

words = ["pear", "fig", "apple"]
print(sorted(words, reverse=True))
try:
    sorted(words, key=lambda w: -w)
except TypeError as e:
    print(f"TypeError: {e}")

2: reverse=True: sort ascending as normal, then reverse the final result.
3: key=lambda x: -x: compare negated values directly — descending on the ORIGINAL values falls out as a side effect.
8: A string has no numeric negation — -w is a TypeError before sorting even begins.

Output

[5, 4, 3, 1, 1]
[5, 4, 3, 1, 1]
['pear', 'fig', 'apple']
TypeError: bad operand type for unary -: 'str'

Why this works: Both approaches agree exactly for the numbers ([5, 4, 3, 1, 1]). reverse=True still works fine on strings, since it only reverses the final order — but -w fails immediately, since strings do not support unary negation.

Remember: For a single field, prefer reverse=True — it works on anything sortable. Reach for negation only when one field of a multi-key tuple needs to go descending while another stays ascending.

`functools.cmp_to_key` for legacy comparator-style sorting

referencebeginner

functools.cmp_to_key wraps an old-style comparator — a function taking two items and returning negative, zero, or positive — into something sorted()'s key= parameter can use, for logic that genuinely cannot be reduced to one value per element.

What we're doing: Sort words by length, then alphabetically among words of the same length, using an explicit comparator.

cmp_to_key.pypython

from functools import cmp_to_key


def compare_by_length_then_alpha(a, b):
    if len(a) != len(b):
        return len(a) - len(b)
    return -1 if a < b else (1 if a > b else 0)


words = ["banana", "fig", "date", "kiwi"]
print(sorted(words, key=cmp_to_key(compare_by_length_then_alpha)))

4: Negative means a comes first, positive means b comes first, zero means either order is fine — the classic C-style comparator contract.
8: cmp_to_key wraps the whole comparator into a single object sorted() accepts as key=.

Output

['fig', 'date', 'kiwi', 'banana']

Why this works: "fig" (length 3) sorts first. "date" and "kiwi" (both length 4) tie on length, so the comparator falls through to alphabetical order, putting "date" before "kiwi". "banana" (length 6) sorts last.

Remember: cmp_to_key is a bridge for comparator logic that genuinely needs both items at once — reach for a plain key= function first, since it is both simpler and faster.