Calculating the kth largest distance among $n$ points on a number line in $O(n\log n)$?
Given some pivot $K$, you can count the pairs with differences above it in $O(n)$, whether you use a random pivot or binary search.

The pairs form a kind of uneven grid in the plane, and you can search diagonally along the line $y = K+x$ to find the border between $x_j - x_i \le K$ and $x_j - x_i \gt K$ in $O(n)$ as follows (Bresenham's Line Drawing Algorithm):


Start at the y axis and find minimum $j$ so that $x_j - x_0 &gt; K$
$Count = n-j+1$
For $i = 1$ to $n-1$ do

While $x_j - x_i &lt; K$, $j = j+1$

If $j=n$ break

$Count = Count + n - j + 1$


(There are some adjustments for when K is larger than the range, but the main idea is here.)

Basically you move right and then slide $j$ up until you cross the line, then add all the entries above that point to the count. As you continue right you're always at or above the $j$ you used in the previous column, so you do $O(n)$ pair tests for the whole scan.