iii. Sorting, Selection and Inversions

In contests you almost never write a sort. What you do need: the right comparator, linear-time sorts when keys are small, partitioning, selection, inversion counting, coordinate compression, and the facts about sortedness that turn into problem solutions.

The algorithms in one table

Algorithm	Time	Space	Stable	Notes
std::sort (introsort)	$O(n\log n)$ worst	$O(\log n)$	no	quicksort + heapsort fallback + insertion sort for small ranges
std::stable_sort	$O(n\log n)$	$O(n)$	yes	merge sort; $O(n{\log }^{2}n)$ if memory is unavailable
merge sort	$O(n\log n)$	$O(n)$	yes	counting cross pairs during merges (inversions, CDQ)
heapsort	$O(n\log n)$	$O(1)$	no	poor cache behaviour
insertion sort	$O(n+\mathrm{inv})$	$O(1)$	yes	fastest for tiny or nearly-sorted arrays
counting sort	$O(n+U)$	$O(n+U)$	yes	keys in $[0,U)$
LSD radix sort	$O(\frac{w}{b}(n+2^b))$	$O(n+2^b)$	yes	32-bit keys in 4 byte passes; beats std::sort 2-4x for $n\ge 10^6$
bucket sort	$O(n)$ expected	$O(n)$	—	only for random-ish real keys

The lower bound: a comparison sort distinguishes $n!$ orders, so it needs ${\log }_{2}n!=n{\log }_{2}n-1.44n+O(\log n)$ comparisons in the worst case. Counting and radix sort beat it by using the key values, not comparisons.

Why each sort is (or isn’t) stable, briefly: merge sort takes from the left half on ties (<=, not <); counting/radix sort place elements by scanning backward through the input during placement, which preserves the original relative order of equal keys; selection and quicksort can jump an equal element past others via a swap, so neither is stable by default; heapsort’s root-swap is likewise order-destroying. Why heapsort is $O(n)$ to build, not $O(n\log n)$: bottom-up heapify (sift down from n/2-1 to 0) does $O(1)$ amortized work per node rather than $O(\log n)$, since most nodes are near the bottom and sift only a short distance — cheaper than $n$ sequential inserts.

Comparators that come up

// fractions a/b with b > 0, compared exactly
sort(all(v), [](auto& x, auto& y) { return (i128)x.a * y.b < (i128)y.a * x.b; });
// strings concatenated to the smallest number: order by a+b < b+a (transitive, provably)
sort(all(s), [](const string& a, const string& b) { return a + b < b + a; });
// by angle around the origin without atan2: half-plane first, then cross product
auto half = [](P p) { return p.y < 0 || (p.y == 0 && p.x < 0); };
sort(all(pts), [&](P a, P b) { return half(a) != half(b) ? half(a) < half(b) : a.cross(b) > 0; });
// indices by key (argsort)
vector<int> id(n); iota(all(id), 0); sort(all(id), [&](int i, int j) { return a[i] < a[j]; });

Exchange-argument sorts (job scheduling, greedy merges) need the derived relation to be transitive; check it on random triples if in doubt.

Proof: the string-concatenation comparator is a valid (transitive) order

Define $a⪯b$ by $a+b\le b+a$ (lexicographic). This is equivalent to comparing the infinite periodic extensions $a^{\infty }=aaa\dots$ and $b^{\infty }=bbb\dots$ lexicographically: standard fact about periodic strings, since $a+b$ and $b+a$ have the same length $|a|+|b|$, and the first position where $a^{\infty }$ and $b^{\infty }$ differ (if any, within, say, the first $\mathrm{lcm}(|a|,|b|)$ or simply the first $|a|+|b|$ characters, which suffices to detect any difference between two periodic sequences with periods $|a|,|b|$) occurs at the same relative position and with the same outcome as the first difference between $a+b$ and $b+a$ — a short case check on whether that position falls in the $a$-part or $b$-part of each concatenation confirms the two comparisons always agree. Since $⪯$ is then literally “compare two fixed infinite sequences $a^{\infty },b^{\infty }$ lexicographically”, and ordinary lexicographic order on sequences is transitive, $⪯$ is transitive. $■$

Partitioning and selection

Three-way partition (Dutch national flag). Invariant: [0, lt) < pivot, [lt, i) = pivot, [i, gt] unknown, (gt, n) > pivot. When swapping with gt, don’t advance i, because the incoming element is unexamined.

void partition3(vector<int>& a, int l, int r, int p, int& lt, int& gt) {  // [l, r]
    int i = l; lt = l; gt = r;
    while (i <= gt) {
        if (a[i] < p) swap(a[lt++], a[i++]);
        else if (a[i] > p) swap(a[i], a[gt--]);
        else i++;
    }
}

Quicksort with a random pivot and three-way partition is $O(n\log n)$ expected even with many equal keys. Hoare’s two-way partition does about 3x fewer swaps than Lomuto’s.

Proof: the three-way partition invariant is maintained

Before the loop, lt=i=l and gt=r, so the three nontrivial regions [l,lt), [lt,i), (gt,r] are all empty and [i,gt] is the whole range — the invariant holds vacuously. Each iteration examines a[i]: if a[i]<p, swapping it into a[lt] is safe because a[lt] (the first element of the “=p” region, or a[i] itself if that region is empty) becomes the new last element of an extended “<p” region, while the incoming value at position i is exactly the old a[lt], which is =p by the invariant — so incrementing both lt and i extends the “<p” region and keeps the “=p” region’s content valid; if a[i]==p, it’s already correctly placed at the boundary, so only i advances, extending “=p”; if a[i]>p, swapping it to a[gt] extends the “>p” region by one, but the element swapped in from gt is unexamined, so i must not advance (it is examined again next iteration). In every case one region grows by exactly one element and the unprocessed region [i,gt] shrinks by exactly one, so the invariant persists and the loop terminates (unprocessed region strictly shrinks) with [i,gt] empty, i.e. everything correctly partitioned into <p, =p, >p. $■$

Named uses: “sort colors” (3 fixed values), segregating even/odd or sign with a simplified 2-way version, wiggle sort, and $k$-way generalisations with counting sort or more pointers.

Selection ($k$-th smallest):

Method	Cost
nth_element(a.begin(), a.begin() + k, a.end())	$O(n)$ expected; afterwards $a_k$ is in place, smaller to its left, larger to its right
quickselect, random pivot	$O(n)$ expected; recurse into one side only
median of medians	$O(n)$ worst case: groups of 5, $T(n)=T(n/5)+T(7n/10)+O(n)$
partial_sort	top $k$ sorted in $O(n\log k)$
heap of size $k$	streaming top-$k$, $O(n\log k)$
two heaps	running median, $O(\log n)$ per insert (Heaps)
order-statistic tree / BIT descent	dynamic $k$-th, $O(\log n)$
wavelet tree / persistent segment tree	$k$-th in a subarray (Range Order Statistics)

Selection on a sorted matrix or on pairwise sums is binary search on the value with a counting check (Binary Search), or Frederickson’s $O(n)$ method on sorted matrices.

Selection pitfalls

nth_element takes the iterator to position $k$, not $k+1$. A fixed or first-element pivot (quickselect or quicksort) gets hacked on Codeforces — sorted or adversarial input forces $O(n^2)$ — always randomise the pivot. The median of an even-length array needs an explicit choice of lower vs. upper median.

Inversions

An inversion is a pair $i<j$ with $a_i>a_j$.

• The minimum number of adjacent swaps to sort is the inversion count.
• The minimum number of arbitrary swaps to sort a permutation is $n-(\text{number of cycles})$.
• Each swap of two elements changes the inversion count’s parity, so the sign of a permutation is $(-1{)}^{\mathrm{inv}}=(-1{)}^{n-\text{cycles}}$.
• Over all permutations the expected number of inversions is $\frac{n(n-1)}{4}$.

Proof: the four inversion facts above

Adjacent swaps = inversion count. Each adjacent swap changes the relative order of exactly one pair, so it changes $\mathrm{inv}$ by exactly $\pm 1$; sorting needs $\mathrm{inv}\to 0$, so at least $\mathrm{inv}$ swaps are needed. Exactly $\mathrm{inv}$ suffice: repeatedly swap any adjacent inverted pair (one exists whenever $\mathrm{inv}>0$, since a non-sorted sequence has some adjacent descent), which strictly decreases $\mathrm{inv}$ by 1 each time (bubble sort’s correctness).
Arbitrary swaps $=n-c$ ($c$ = number of cycles). A swap of two elements in different cycles merges them into one cycle (decreasing the cycle count by 1); a swap within one cycle of length $\ell \ge 2$ splits it into two cycles (increasing the count by 1). To reach the identity ($n$ cycles, all length 1), starting from $c$ cycles, every swap changes $c$ by exactly $\pm 1$, and only merging swaps (decreasing a cycle toward length 1, eventually) make progress — the minimum sequence uses exactly one merge-type swap per “extra” element needed to split each cycle down to fixed points, giving exactly ${\sum }_{\text{cycles}}({\ell }_i-1)=n-c$ swaps (and this many always suffice: fix cycles one at a time, each needing ${\ell }_i-1$ swaps to resolve).
Sign formula. Each swap (adjacent or not, a transposition) changes the permutation’s sign by $-1$ (a classical fact: a transposition is an odd permutation). So after $k$ transpositions from the identity, $\mathrm{sign}=(-1{)}^k$; taking $k=\mathrm{inv}$ (adjacent swaps) or $k=n-c$ (arbitrary swaps) — both valid swap sequences reaching the same permutation — gives $(-1{)}^{\mathrm{inv}}=(-1{)}^{n-c}$, consistent since any two sequences of transpositions reaching the same permutation have the same parity of length (sign is well-defined).
Expected inversions $=n(n-1)/4$. By linearity of expectation over the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs, each pair $(i,j)$, $i<j$, is inverted with probability exactly $\frac{1}{2}$ (symmetry: $a_i>a_j$ and $a_i<a_j$ are equally likely for a uniform random permutation), so $\mathbb{E}[\mathrm{inv}]=\left(\genfrac{}{}{0ex}{}{n}{2}\right)\cdot \frac{1}{2}=\frac{n(n-1)}{4}$. $■$

Tested: all four facts checked by brute force (exact inversion/cycle counts and sign, compared against a reference permutation-sign computation; expected inversions estimated by Monte Carlo over random permutations) for small $n$.

• The number of permutations with exactly $k$ inversions has generating function ${\prod }_{i=1}^n(1+x+\cdots +x^{i-1})$. That’s an $O(nk)$ DP with prefix sums, or $O(k\sqrt{k})$ using Euler’s pentagonal theorem for large $n$.
• The minimum adjacent swaps to turn $a$ into $b$ (same multiset): map each value of $a$ to its target position in $b$ (equal values matched in order), then count inversions.

ll countInv(vector<int>& a, int l, int r, vector<int>& buf) {    // [l, r), sorts a
    if (r - l < 2) return 0;
    int m = (l + r) / 2;
    ll res = countInv(a, l, m, buf) + countInv(a, m, r, buf);
    int i = l, j = m, k = l;
    while (i < m || j < r)
        if (j == r || (i < m && a[i] <= a[j])) buf[k++] = a[i++];
        else res += m - i, buf[k++] = a[j++];
    copy(buf.begin() + l, buf.begin() + r, a.begin() + l);
    return res;
}

The Fenwick version (scan left to right, add i - prefix(a[i])) is shorter after compression. Variants:

Question	Technique
pairs $i<j$ with $a_i>c\cdot a_j$	two pointers inside the merge step
inversions after each cyclic shift of a permutation	moving the first value $x$ to the end changes the count by $(n-x)-(x-1)$
inversions of many subarrays	Mo + BIT $O(n\sqrt{q}\log n)$; or second-offline Mo / block precomputation $O(n\sqrt{n})$
inversions with point updates	BIT of sorted blocks, or CDQ in $O(n{\log }^{2}n)$
Kendall tau distance between rankings	inversions of $b^{-1}\circ a$

Coordinate compression

vector<ll> xs = values;                                  // include every value that will be queried
sort(all(xs)); xs.erase(unique(all(xs)), xs.end());
auto id = [&](ll x) { return int(lower_bound(all(xs), x) - xs.begin()); };

• Collect all values first: array values, query endpoints, thresholds, derived values such as $x\pm 1$.
• For intervals, compressing only endpoints merges distinct gaps. Use half-open $[l,r+1)$ and insert both $l$ and $r+1$, or keep the real length xs[i+1] - xs[i] of each compressed cell and weight by it (rectangle union).
• If keys arrive online and can’t be collected first, use a dynamic segment tree or a hash map.
• “Compress, then index a BIT by value” is one of the most reused pairs in CP: inversions, dominance counting, LIS with weights, offline 2D queries.
• The technique generalises past numbers to any “map arbitrary keys to a dense range”: strings (sort and rank, or map<string,int>), pairs, graph vertices given by arbitrary labels, time points in an offline sweep, or states in a sparse-state-space DP.

Facts about sorted order

• Sorting makes “all pairs” conditions local: the minimum $|a_i-a_j|$ is between neighbours; the number of pairs with $a_i+a_j\le X$ needs two pointers.
• Sorting by one key and processing in order (a sweep) turns 2D problems into 1D data-structure problems.
• Rearrangement inequality: $\sum a_i{b}_{\pi (i)}$ is maximised when both are sorted the same way and minimised when sorted oppositely.

Proof: the rearrangement inequality

Take any arrangement that is not sorted the same way: there exist indices $i<j$ with $a_i<a_j$ but $b_{\pi (i)}>b_{\pi (j)}$ (an “inversion” between the two sequences’ relative order). Swapping $\pi (i)$ and $\pi (j)$ changes the sum by $(a_i{b}_{\pi (j)}+a_j{b}_{\pi (i)})-(a_i{b}_{\pi (i)}+a_j{b}_{\pi (j)})=(a_j-a_i)(b_{\pi (i)}-b_{\pi (j)})>0$ (both factors positive) — strictly increasing the sum. So any arrangement with such an inversion is not maximal; repeating removes all such inversions, reaching the same-order arrangement, which must therefore be the (unique, up to ties) maximum. The minimum follows symmetrically (swapping removes an inversion of the opposite kind only when sorted oppositely is suboptimal, so by the same exchange argument run in the other direction, oppositely-sorted is the minimum). $■$

• A sequence can be sorted by a stack (one push/pop pass) iff it avoids the pattern 231, and with two stacks or a deque the conditions are more complex (pattern classes).
• Sorting $n$ elements with an oracle that compares in $O(1)$: about $n{\log }_{2}n$ queries with merge sort or binary insertion. Ford-Johnson (merge insertion) is near optimal for small $n$.
• Sorting networks: Batcher’s odd-even merge sort and bitonic sort use $O(n{\log }^{2}n)$ comparators of fixed pattern (branchless, SIMD-friendly). The 0-1 principle: a network sorts all inputs iff it sorts all 0/1 inputs.
• Pancake sorting (prefix reversals): at most $2n-3$ with the obvious greedy. Sorting by adjacent transpositions: inversions. Sorting by arbitrary transpositions: $n-$ cycles. Sorting by block moves or reversals with signs: research problems; brute force with BFS for small $n$.