algo-sorting

name	algo-sorting
description	Sorting — when to call the built-in, when to roll your own (counting / radix / heap), stability, custom comparators.
when-to-use	Pre-sort for two-pointer / binary-search, top-k via heap, kth-smallest via quickselect, custom-key ordering.

Sorting — sort() first, custom rarely

Python's list.sort and JavaScript's Array.prototype.sort are both Timsort variants — O(n log n) worst case, stable. Reach for a custom sort only when you need a different time/space trade (counting sort for small integer ranges) or you cannot afford the copy (heap-based top-k).

Invariants

• Stable sort: equal-key elements retain their original relative order. Both list.sort() and recent Array.prototype.sort are stable; older JS engines were not (pre-2019).
• In-place sort returns None in Python (list.sort); use sorted() for a new list. JS arr.sort() mutates and returns the array.
• Sorting by multiple keys: sort by least-significant key first, then by next, taking advantage of stability. Or use a tuple key.

Complexity

• Built-in (Timsort): O(n log n) worst, O(n) best on near-sorted input.
• Quickselect (kth element): O(n) average, O(n^2) worst.
• Heap-based top-k: O(n log k) time, O(k) extra space.
• Counting sort: O(n + r) for value range r — beats comparison sort when r is small (e.g. 0..255).
• Radix sort: O(n × d) for d digits — strings of bounded length, fixed-precision integers.

Template — Python (multi-key custom comparator via tuple key)

# Sort by score descending, then by name ascending. Stability is
# implicit: equal-tuple rows keep insertion order.
records.sort(key=lambda r: (-r.score, r.name))

# Stability lets you also chain single-key sorts:
records.sort(key=lambda r: r.name)         # secondary
records.sort(key=lambda r: r.score, reverse=True)  # primary

Use a tuple key when you can — it is cleaner and roughly twice as fast as functools.cmp_to_key. Reach for cmp_to_key only when the comparison is non-transitive in tuple form (rare; one classic case is "biggest-number-by-concatenation").

Template — Python (heap-based top-k)

import heapq

def top_k_largest(arr: list[int], k: int) -> list[int]:
    """The ``k`` largest elements (in arbitrary order)."""
    if k <= 0: return []
    return heapq.nlargest(k, arr)

def top_k_smallest_by_key(items, k, key):
    return heapq.nsmallest(k, items, key=key)

heapq.nsmallest/nlargest are O(n log k) and avoid sorting the whole list when k << n.

Template — JavaScript (custom comparator, stable since 2019)

// Numeric sort — default is lexicographic, which is wrong for numbers.
arr.sort((a, b) => a - b);

// Multi-key: descending score, then ascending name.
records.sort((a, b) => b.score - a.score || a.name.localeCompare(b.name));

localeCompare is the right tool for human-language strings. For ASCII identifiers, the </> operators are faster.

Common pitfalls

• JavaScript default sort is lexicographic. [10, 2, 1].sort() gives [1, 10, 2]. Always pass a comparator for numbers.
• Mutating during iteration. for i in range(len(arr)): if pred(arr[i]): arr.remove(...) shifts indices and skips elements. Sort first and walk with a write index instead.
• list.sort() returns None in Python. x = arr.sort() sets x = None. Use sorted(arr) to get a new list.
• Comparator returning bool. JS sort((a, b) => a > b) returns true/false (1/0 in numeric coercion) — non-transitive, breaks stability. Return a - b or cmp(a, b).
• Stability assumed but not provided. On older runtimes, equal keys may shuffle. If correctness depends on it, augment the key with the original index.
• Sort + binary search on objects with mutating fields. If a later edit mutates the sort key, the array is no longer sorted.

Test corner cases

• Empty array.
• Single-element array.
• Already sorted (best case).
• Reverse sorted (worst case for naive quicksort).
• All-equal values (stability matters here — verify).
• Mixed types (numbers + strings) — coerces and gives surprising results. Always sort homogeneous data.
• Floats with NaN — comparisons with NaN return false, leading to undefined order. Filter NaNs first.

For "median in a stream", reach for two heaps (min + max). For "kth smallest", quickselect or nsmallest is faster than sort+index.