Sorting Algorithms

Updated

October 31, 2026

Sorting Algorithms

Sorting organizes collections into ascending or descending sequence so that subsequent searches, deduplications, and range scans can execute in logarithmic time. In Python, the boring default is the built-in list.sort() and sorted(), which use Timsort—an adaptive hybrid of Merge Sort and Insertion Sort written in C. Studying classical sorting algorithms reveals the mechanics of partitioning, recursion, and stability.

Divide and Conquer Sorting

Mental model

Comparison-based sorting algorithms navigate trade-offs between speed, space, and stability:

Algorithm Best Time Average Time Worst Time Space Stable? Primary Use Case
Insertion Sort \(O(n)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) Yes Small datasets (\(n < 30\)) or nearly-sorted streams
Merge Sort \(O(n \log n)\) \(O(n \log n)\) \(O(n \log n)\) \(O(n)\) Yes Guaranteed \(O(n \log n)\) performance and stable ordering
Quicksort \(O(n \log n)\) \(O(n \log n)\) \(O(n^2)\) \(O(\log n)\) No Memory-constrained systems needing in-place speed
Python Timsort \(O(n)\) \(O(n \log n)\) \(O(n \log n)\) \(O(n)\) Yes Python standard default (list.sort() / sorted())

Stable Sorting

A sort is stable if elements with identical keys appear in the output in the same relative order as in the input. For example, sorting desk orders by price without scrambling their arrival times requires a stable sort.

Merge Sort Divide and Conquer:
[ 38, 27, 43, 3, 9, 82, 10 ]
        /            \
[ 38, 27, 43, 3 ]    [ 9, 82, 10 ]   <- Divide
        \            /
[ 3, 27, 38, 43 ]    [ 9, 10, 82 ]   <- Conquer (Merge Sorted Sublists)
              \        /
  [ 3, 9, 10, 27, 38, 43, 82 ]       <- Fully Sorted

Worked examples

Case 1: Adaptive Insertion Sort for nearly-sorted batches

Save as insertion_sort.py. Implement insertion sort and show how it runs in linear \(O(n)\) time when items are already largely sorted.

# insertion_sort.py
def insertion_sort[T](items: list[T]) -> list[T]:
    # Mutates in place
    n = len(items)
    for i in range(1, n):
        key = items[i]
        j = i - 1
        # Shift elements greater than key to the right
        while j >= 0 and items[j] > key:
            items[j + 1] = items[j]
            j -= 1
        items[j + 1] = key
    return items


def main() -> None:
    # Nearly sorted desk arrivals
    arrivals = [101, 102, 105, 103, 104, 106]
    print(f"Before insertion sort: {arrivals}")

    insertion_sort(arrivals)
    print(f"After insertion sort:  {arrivals}")


if __name__ == "__main__":
    main()

Run:

uv run python insertion_sort.py

Output:

Before insertion sort: [101, 102, 105, 103, 104, 106]
After insertion sort:  [101, 102, 103, 104, 105, 106]

Case 2: Stable Divide-and-Conquer Merge Sort

Save as merge_sort.py. Implement generic stable merge sort.

# merge_sort.py
def merge_sort[T](items: list[T]) -> list[T]:
    if len(items) <= 1:
        return items

    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])

    return _merge(left, right)


def _merge[T](left: list[T], right: list[T]) -> list[T]:
    result: list[T] = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= preserves stability
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result


def main() -> None:
    prices = [45, 12, 85, 32, 89, 39, 69, 44, 42, 1, 45]
    print(f"Unsorted prices: {prices}")

    sorted_prices = merge_sort(prices)
    print(f"Sorted prices:   {sorted_prices}")


if __name__ == "__main__":
    main()

Run:

uv run python merge_sort.py

Output:

Unsorted prices: [45, 12, 85, 32, 89, 39, 69, 44, 42, 1, 45]
Sorted prices:   [1, 12, 32, 39, 42, 44, 45, 45, 69, 85, 89]

Case 3: In-Place Quicksort with Lomuto Partition

Save as quick_sort.py. Implement in-place quicksort.

# quick_sort.py
def quick_sort[T](items: list[T]) -> None:
    def _sort(low: int, high: int) -> None:
        if low < high:
            p = _partition(low, high)
            _sort(low, p - 1)
            _sort(p + 1, high)

    def _partition(low: int, high: int) -> int:
        pivot = items[high]
        i = low
        for j in range(low, high):
            if items[j] < pivot:
                items[i], items[j] = items[j], items[i]
                i += 1
        items[i], items[high] = items[high], items[i]
        return i

    _sort(0, len(items) - 1)


def main() -> None:
    order_ids = [84, 12, 91, 45, 33, 72, 16, 50]
    print(f"Before quicksort: {order_ids}")

    quick_sort(order_ids)
    print(f"After quicksort:  {order_ids}")


if __name__ == "__main__":
    main()

Run:

uv run python quick_sort.py

Output:

Before quicksort: [84, 12, 91, 45, 33, 72, 16, 50]
After quicksort:  [12, 16, 33, 45, 50, 72, 84, 91]

The trap

The biggest trap in Python is writing custom sorting routines for production systems. Pure Python loops run in bytecode interpreted by the CPython VM. Python’s built-in list.sort() and sorted() are implemented directly in optimized C (Timsort), which outperforms pure Python sorting algorithms by 20x to 50x while guaranteeing stability and \(O(n \log n)\) worst-case execution.

# bad_custom_sort_benchmark.py
import random
import time


def main() -> None:
    data = [random.randint(1, 100_000) for _ in range(20_000)]

    # Custom pure-Python Quicksort
    copy1 = data[:]
    t0 = time.perf_counter()
    # Simple recursive quicksort
    def py_qs(arr: list[int]) -> list[int]:
        if len(arr) <= 1:
            return arr
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        return py_qs(left) + middle + py_qs(right)

    _ = py_qs(copy1)
    py_time = time.perf_counter() - t0

    # Built-in C-level Timsort
    copy2 = data[:]
    t1 = time.perf_counter()
    copy2.sort()
    c_time = time.perf_counter() - t1

    print(f"Custom Python sort: {py_time:.4f} seconds")
    print(f"Built-in list.sort: {c_time:.4f} seconds ({py_time / c_time:.1f}x faster!)")


if __name__ == "__main__":
    main()

Run:

uv run python bad_custom_sort_benchmark.py

Output:

Custom Python sort: 0.0152 seconds
Built-in list.sort: 0.0018 seconds (8.4x faster!)

The boring rule

  1. Always use my_list.sort() (in-place) or sorted(iterable) (returns new list) in production.
  2. Use the key= parameter (e.g. key=lambda x: x.price) rather than custom comparison methods.
  3. Python’s sorting is guaranteed stable—items with equal keys preserve their original sequence.
  4. To sort in descending order, pass reverse=True.

Try this

  1. Sort a list of desk ticket dictionaries first by status (alphabetically) and then by priority (numerically) using Python’s stable tuple sorting key: key=lambda t: (t['status'], t['priority']).
  2. Benchmark insertion_sort against list.sort() on an already sorted list of 10,000 numbers. Notice how Timsort’s natural galloping mode recognizes the pre-sorted sequence in linear \(O(n)\) time.