Sorting, Selection & Divide-and-Conquer

Selection contract

One-based k becomes absolute target k-1. Duplicates occupy separate ranks; in-place mutation is allowed.

Four partition regions

[lo,lt) < p; [lt,i) = p; [i,gt] unknown; (gt,hi] > p. A swap from the unknown right end does not advance i. Worked: [4,2,4,1,3], pivot 4 → [2,1,3,4,4]. Target 3 returns 4.

Cost depends on the pivot

Random pivots give expected O(n), not guaranteed half splits. Worst case is O(n²); three-way partition handles duplicate regions together.

Count while merging

Recursive result: sorted segment plus its original inversion count. [5,1,4,2]: child counts 1+1; merge [1,5] with [2,4] adds 2. Total 4. On a right value smaller than left[i], add the unmerged left count. Equality adds zero.

Reconstruct independently

Partition [2,5,2,1] around 2; classify the swapped-in 1 before advancing. Merge [1,4,4] with [2,4]: cross count 2. Validate small arrays against sorted ranks and a quadratic inversion oracle.