Sorting Algorithms

Overview

This subpackage provides two comparison sorts, chosen because they sit at opposite ends of the classic trade-offs:

  • Merge sort is stable and returns a new list; it runs in \(O(n \log n)\) whatever the input, at the cost of \(O(n)\) extra memory.

  • Quicksort sorts in place with \(O(\log n)\) extra memory and is usually faster in practice, but it is not stable and its worst case is \(O(n^2)\).

Both accept the key and reverse keywords of the built-in sorted(), and both operate on a Python list only.

Note

Why a list and not a linked list? Both algorithms rely on indexed access. On a linked list, structure[i] walks the chain and costs \(O(n)\), which would turn an \(O(n \log n)\) sort into an \(O(n^2 \log n)\) one. To sort the content of a linear structure, convert it first with sds.linear.to_list() and rebuild it with sds.linear.from_list().

Mathematical Foundation

A comparison sort only learns about the order of its input by comparing pairs of keys. Any such algorithm can be pictured as a binary decision tree whose leaves are the \(n!\) possible orderings, so its height, the worst-case number of comparisons, satisfies

\[h \;\geq\; \log_2(n!) \;=\; \Theta(n \log n).\]

Merge sort meets this bound in every case, and quicksort meets it on average: neither can be improved by more than a constant factor without leaving the comparison model.

A sort is stable if items with equal keys keep their original relative order. Stability matters when sorting by one key after another: sorting records by name, then stably by department, yields records ordered by department and, within a department, by name.

Merge Sort

        graph TD
    A["[5, 2, 4, 1]"] --> B["[5, 2]"]
    A --> C["[4, 1]"]
    B --> D["[5]"]
    B --> E["[2]"]
    C --> F["[4]"]
    C --> G["[1]"]
    D --> H["[2, 5]"]
    E --> H
    F --> I["[1, 4]"]
    G --> I
    H --> J["[1, 2, 4, 5]"]
    I --> J

    style A fill:#3498db,color:#fff
    style J fill:#2ecc71,color:#fff

The input is split in halves down to single elements (top), then the sorted halves are merged back pairwise (bottom). When the two candidates of a merge compare equal, the element of the left half is taken first, which is exactly what makes the algorithm stable.

sds.algorithms.sorting.merge_sort(items, *, key=None, reverse=False)[source]

Return a new list with the items of items in sorted order.

Parameters:

  • items (list) – The list to sort. It is not modified.

  • key (callable, optional) – Function of one argument extracting the comparison key from each item, as for sorted(). It is called exactly once per item.

  • reverse (bool, optional) – If True, sort in descending order. Stability is preserved: equal items still keep their original relative order.

Returns:

A new sorted list.

Return type:

list

Raises:

StructureTypeError – If items is not a list, or if two keys cannot be compared.

Examples

>>> merge_sort([5, 2, 4, 1])
[1, 2, 4, 5]
>>> merge_sort(["bb", "a", "cc", "d"], key=len)
['a', 'd', 'bb', 'cc']
>>> merge_sort([1, 3, 2], reverse=True)
[3, 2, 1]

Notes

Time complexity: O(n log n) in the best, average and worst case. Space complexity: O(n) for the merged lists, plus O(log n) recursion depth.

Keys are computed once up front and carried alongside each item, so items themselves are never compared and key is never called twice for the same element.

Quicksort

        graph TD
    A["[5, 2, 8, 1, 9, 3]<br/>pivot = median(5, 8, 3) = 5"] --> B["[3, 2, 1] ≤ 5"]
    A --> C["[9, 8, 5] ≥ 5"]
    B --> D["[1, 2, 3]"]
    C --> E["[5, 8, 9]"]
    D --> F["[1, 2, 3, 5, 8, 9]"]
    E --> F

    style A fill:#3498db,color:#fff
    style F fill:#2ecc71,color:#fff

Each partition step moves keys that come before the pivot to the left and keys that come after it to the right, then both parts are sorted independently. The implementation combines three standard refinements: Hoare partitioning (robust to many equal keys), a median-of-three pivot (sorted and reverse-sorted inputs are no longer worst cases), and recursion on the smaller part only (the call stack stays \(O(\log n)\) deep).

sds.algorithms.sorting.quick_sort(items, *, key=None, reverse=False)[source]

Sort items in place.

Like list.sort(), the function returns None to make it clear that the argument itself was modified.

Parameters:

  • items (list) – The list to sort, modified in place.

  • key (callable, optional) – Function of one argument extracting the comparison key from each item, as for list.sort(). It is called exactly once per item.

  • reverse (bool, optional) – If True, sort in descending order.

Raises:

StructureTypeError – If items is not a list, or if two keys cannot be compared.

Examples

>>> data = [5, 2, 4, 1]
>>> quick_sort(data)
>>> data
[1, 2, 4, 5]
>>> words = ["ccc", "a", "bb"]
>>> quick_sort(words, key=len, reverse=True)
>>> words
['ccc', 'bb', 'a']

Notes

Time complexity: O(n log n) on average, O(n²) in the worst case (made unlikely, not impossible, by the median-of-three pivot). Space complexity: O(log n) recursion depth; O(n) additional when key is given, for the precomputed keys.

The sort is not stable: items with equal keys may end up in any relative order. Three records sharing one key are enough to show it:

>>> records = [(0, "a"), (0, "b"), (0, "c")]
>>> quick_sort(records, key=lambda r: r[0])
>>> records
[(0, 'a'), (0, 'c'), (0, 'b')]

When the order of ties matters, use merge_sort(), which is stable and O(n log n) in every case. To sort a list in place and stably, assign the result back into the same list object:

items[:] = merge_sort(items, key=key)

A stable quicksort would need O(n) extra memory to break ties by original position, losing its only advantage over merge sort while keeping its O(n²) worst case, so none is provided.

Warning

quick_sort is not stable: three records with the same key are enough for it to reorder them. When the order of ties matters, use merge_sort. To get a stable sort that still updates the caller’s list object, assign the result back into it:

records[:] = merge_sort(records, key=lambda r: r.department)

No stable variant of quicksort is provided on purpose: breaking ties by original position would cost \(O(n)\) extra memory, the same as merge sort, while keeping quicksort’s \(O(n^2)\) worst case.

Comparison

Property

merge_sort

quick_sort

Best / average time

\(O(n \log n)\)

\(O(n \log n)\)

Worst-case time

\(O(n \log n)\)

\(O(n^2)\)

Extra space

\(O(n)\)

\(O(\log n)\) (+ \(O(n)\) with key)

Stable

Yes

No

Input

Left unchanged

Sorted in place

Returns

A new list

None

Usage Examples

Sorting records by several keys

Stability lets a secondary order survive a later sort on the primary key:

from sds.algorithms.sorting import merge_sort

staff = [("Lina", "R&D"), ("Ahmed", "Sales"), ("Zoé", "R&D"), ("Bo", "Sales")]

by_name = merge_sort(staff, key=lambda p: p[0])
by_team = merge_sort(by_name, key=lambda p: p[1])
# [('Lina', 'R&D'), ('Zoé', 'R&D'), ('Ahmed', 'Sales'), ('Bo', 'Sales')]

Sorting a large list in place

import random
from sds.algorithms.sorting import quick_sort

data = [random.random() for _ in range(100_000)]
quick_sort(data)            # data is now sorted; nothing is returned
quick_sort(data, reverse=True)

Sorting a linear structure

from sds.linear import Queue, from_list, to_list
from sds.algorithms.sorting import merge_sort

queue = from_list(Queue, [3, 1, 2])
queue = from_list(Queue, merge_sort(to_list(queue)))
print(to_list(queue))       # [1, 2, 3]

Best Practices

✅ Use merge_sort when equal keys must keep their order, or when the original list must stay untouched.

✅ Use quick_sort when memory matters and stability does not.

✅ Need both stability and an in-place update? Write items[:] = merge_sort(items).

✅ Pass key rather than pre-building (key, item) tuples: the key is computed once per item and items themselves are never compared.

❌ Do not pass a linked structure directly; convert it with to_list() first.

References