Count how many pairs of positions in a list have values adding up to strictly less than a limit.

count_pairs_below([1, 2, 3, 4], 6)  # 4

The pairs are 1+2, 1+3, 1+4 and 2+3.

Sort first, then place left at the smallest value and right at the largest.

• If values[left] + values[right] < limit, then left pairs successfully with every position from left + 1 through right, because those values are all no larger. That is right - left pairs at once. Move left up.
• Otherwise the largest value is too big to pair with left or anything after it. Move right down.

Each step moves a pointer, so the pass is linear. Remember to sort a copy, since the input belongs to the caller.

Write count_pairs_below(numbers, limit) returning the number of index pairs i < j with numbers[i] + numbers[j] < limit, in O(n log n) time and without changing the input.

The explanation opens here once every check passes.