Sorting, Selection & Divide-and-Conquer

You will implement QuickselectKth(nums, k) with a one-based rank and CountInversions(nums), which counts strictly out-of-order index pairs. Be ready to trace indices in a mutable array and merge two sorted sequences. If partition boundaries are unfamiliar, draw the four regions below before writing a loop.

Partition is a contract, not a complete sort

Selection only needs to know which region contains the requested rank. For a pivot value p, maintain four regions while scanning an inclusive active range:

[lo,lt) < p    [lt,i) == p    [i,gt] unknown    (gt,hi] > p

If nums[i] < p, exchange it with nums[lt] and advance both lt and i. If equal, advance i. If greater, exchange it with nums[gt] and decrease gt; do not advance i because the incoming value has not been classified. On termination, [lt,gt] is the equal region. The outer regions are not sorted.

Trace [4,2,4,1,3] with p=4:

Action	Array	lt	i	gt
Start	[4,2,4,1,3]	0	0	4
Equal 4	[4,2,4,1,3]	0	1	4
Move 2 left	[2,4,4,1,3]	1	2	4
Equal 4	[2,4,4,1,3]	1	3	4
Move 1 left	[2,1,4,4,3]	2	4	4
Move 3 left	[2,1,3,4,4]	3	5	4

The fourth-smallest element has target index 3, inside the equal region: return 4. The second-smallest target is index 1, so search only [0,2]. Keep the target as an absolute zero-based index; subtracting an offset is only correct when the recursive API explicitly uses a rank relative to the subarray.

The Go reference uses a different, two-ended partition. Its returned boundaries are not a single pivot's final index. Derive the invariant for whichever scheme you use; do not mix a Lomuto pivot-index recurrence with Hoare-style boundaries. The array may be modified by the exercise.

One branch saves work, but balance still matters

Quicksort recursively sorts both outer regions. Quickselect visits only the region containing the target. With a uniformly randomized pivot, its expected total work is O(n); a random pivot does not guarantee a half split. Repeated extreme splits can still cost O(n²). Three-way partitioning avoids repeated work on a large equal-valued region, including an all-equal array.

The provided deterministic reference is not a worst-case linear algorithm. Randomization reduces sensitivity to a fixed input order, and deterministic linear selection requires a stronger pivot strategy. A full sort answers a single selection query in O(n log n), but misses the algorithm being practiced. An iterative in-place partition uses O(1) auxiliary array storage.

Merge produces both sorted data and a count

CountInversions returns the number of pairs i < j with nums[i] > nums[j]. Equal values never count. Give each recursive call this postcondition:

The half-open segment [lo,hi) is sorted, and the returned count equals the inversions originally contained in that segment.

The parent adds left count, right count and cross count. Each pair belongs to exactly one category. This is why sorting the halves does not lose information: the recursive calls have already counted their internal inversions.

For original [5,1,4,2], the left recursion returns [1,5] and count 1; the right returns [2,4] and count 1. Now merge:

Next left / right	Take	Cross count added	Reason
1 / 2	1	0	1 is not greater than 2
5 / 2	2	1	All remaining left values exceed 2
5 / 4	4	1	All remaining left values exceed 4
5 / exhausted	5	0	No right value remains

Total is 1+1+2=4. When taking a right value smaller than left[i], add the number of unmerged left values, not one and not the full left length. Take left first on equality so equal pairs contribute zero. Reuse an O(n) merge buffer; each level processes O(n) elements for O(n log n) time. The maximum count is n*(n-1)/2; at n=200000 this exceeds 32-bit signed range, hence the Go return type is int64.

Finish a trace before implementing

1. Partition [2,5,2,1] around 2. After moving 5 to the right, which newly arrived value must be examined before i advances? Which rank indices can immediately return 2?
2. Merge [1,4,4] with [2,4]. You have emitted 1 then 2. How many cross inversions did 2 add? What do the equal 4s contribute?
3. Diagnose an implementation that recursively counts each half but never writes the merged order back before its parent runs.

Check the reasoning

1. Swapping 5 with the last element brings 1 to the scan position. Examine it; the final partition is [1,2,2,5], and absolute indices 1 and 2 return 2.
2. Taking 2 adds two cross inversions, one against each left 4. Equal 4s add zero, so the entire cross count is 2.
3. The parent assumes sorted halves to count all remaining left values at once. Without sorted output that implication fails, even if child counts happen to be right.

Implement both exercises without copying a complete solution. Check sorted, reverse-sorted, duplicate-heavy and singleton inputs against a full sort or a quadratic pair counter on small cases. Later, reconstruct a selection trace with k=1 and k=n and explain why every iteration shrinks the unknown region.