Sorting

// Java defense against quicksort worst case on int[]
Integer[] boxed = Arrays.stream(a).boxed().toArray(Integer[]::new);
Arrays.sort(boxed);            // now Timsort, O(n log n) guaranteed

// JavaScript default sorts as strings: [10, 9, 1] -> [1, 10, 9]
nums.sort((x, y) => x - y);    // always pass a comparator for numbers

a.sort()                                  # in place, stable
b = sorted(a)                             # new list
sorted(a, reverse=True)
sorted(words, key=len)
sorted(words, key=str.lower)
sorted(points, key=lambda p: (p[0], -p[1]))     # asc x, then desc y
sorted(d.items(), key=lambda kv: (-kv[1], kv[0]))  # count desc, name asc

# multi-key with mixed directions and non-numeric keys: sort twice,
# least significant first. Stability preserves the earlier order.
people.sort(key=lambda p: p.name)
people.sort(key=lambda p: p.age, reverse=True)

# custom comparator, when a key function cannot express the rule
from functools import cmp_to_key
def cmp(x, y):
    if x + y > y + x:
        return -1        # x first
    if x + y < y + x:
        return 1
    return 0
largest = "".join(sorted(map(str, nums), key=cmp_to_key(cmp)))

list.sort(Comparator.comparingInt(P::age)
                    .thenComparing(P::name)
                    .reversed());
Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));
// Never write (x, y) -> x[0] - y[0], it overflows on large values.

sort(v.begin(), v.end(), [](const P& a, const P& b) {
    if (a.age != b.age) return a.age > b.age;   // strict weak ordering
    return a.name < b.name;
});

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

def merge(x, y):
    out, i, j = [], 0, 0
    while i < len(x) and j < len(y):
        if x[i] <= y[j]:        # <= keeps it stable
            out.append(x[i])
            i += 1
        else:
            out.append(y[j])
            j += 1
    out.extend(x[i:])
    out.extend(y[j:])
    return out

def count_inversions(a):
    """Pairs i < j with a[i] > a[j]. O(n log n) via merge sort."""
    def sort_count(arr):
        if len(arr) <= 1:
            return arr, 0
        mid = len(arr) // 2
        left, cl = sort_count(arr[:mid])
        right, cr = sort_count(arr[mid:])
        merged, i, j, cross = [], 0, 0, 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
                cross += len(left) - i     # left[i:] all exceed right[j]
        merged += left[i:] + right[j:]
        return merged, cl + cr + cross
    return sort_count(a)[1]

import random

def quicksort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    while lo < hi:                      # tail-call elimination by hand
        p = partition(a, lo, hi)
        if p - lo < hi - p:             # recurse on the smaller side
            quicksort(a, lo, p - 1)     # keeps the stack at O(log n)
            lo = p + 1
        else:
            quicksort(a, p + 1, hi)
            hi = p - 1

def partition(a, lo, hi):
    """Lomuto partition with a random pivot."""
    r = random.randint(lo, hi)
    a[r], a[hi] = a[hi], a[r]
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i

def quickselect(a, k):
    """kth smallest, 0-indexed. O(n) average, O(n^2) worst. Mutates a."""
    lo, hi = 0, len(a) - 1
    while True:
        p = partition(a, lo, hi)
        if p == k:
            return a[p]
        if p < k:
            lo = p + 1
        else:
            hi = p - 1

def counting_sort(a, k):
    """Values in 0..k. O(n + k), stable as written."""
    count = [0] * (k + 1)
    for x in a:
        count[x] += 1
    for i in range(1, k + 1):
        count[i] += count[i - 1]        # running positions
    out = [0] * len(a)
    for x in reversed(a):               # reversed keeps it stable
        count[x] -= 1
        out[count[x]] = x
    return out

def radix_sort(a):
    """Non-negative ints, LSD base 256. O(d(n + b))."""
    if not a:
        return a
    out = a[:]
    for shift in range(0, 32, 8):
        buckets = [[] for _ in range(256)]
        for x in out:
            buckets[(x >> shift) & 255].append(x)
        out = [x for b in buckets for x in b]
    return out