1286. Sorting Pairs by Packing Them Into One Key

Sort n pairs (a, b) by a first and by b where a ties. Do it by packing each pair into ONE integer key and sorting the keys, then unpacking.

(2,5) (1,9) (2,1) -> 1 9 2 1 2 5

## What most people try first

A comparator, which is the normal and usually correct answer. Packing wins in three situations worth recognising: when the language's sort over a primitive array is far faster than over objects with a callback, when the keys are to be fed to a radix or counting sort, and when the sorted order has to be stored or transmitted as single values. The idea also appears wherever a composite sort key has to become one value, including database index keys.

The wrong first attempt is a * 1000000000 + b, using a decimal scale. It is not wrong in principle, and it is wrong here: with b reaching 10^9 the scale must EXCEED 10^9, so a * 10^9 + b makes (0, 10^9) and (1, 0) collide at exactly 10^9, and the sort silently treats them as equal.

## The condition the packing must satisfy

Packing preserves the order if and only if comparing the keys numerically gives the same answer as comparing (a, b) lexicographically. With a in the HIGH bits and b in the low bits:

key = (a << 30) | b

that holds exactly when the low field is WIDE ENOUGH that b never spills into a's territory. b reaches 10^9, and 2^30 = 1073741824 is the first power of two above it, so 30 bits is the smallest field that works. With that, a larger means a strictly larger key whatever the b values, because the a part dominates every possible low field; and a equal means the keys differ exactly as the b values do.

A 29-bit field would break it: 2^29 = 536870912 is below 10^9, so b = 10^9 would set a bit inside a's field and (0, 10^9) would outrank (1, 0).

## Width

a reaches 10^9 and sits at offset 30, so the key reaches 10^9 * 2^30 + 10^9, which is about 1.07 * 10^18. That is inside a signed 64-bit integer, whose limit is 9223372036854775807, with a factor of nine to spare, and far past the 2147483647 a signed 32-bit integer holds.

It is also past 2^53 = 9007199254740992 by more than a factor of a hundred, so a JavaScript Number cannot hold the key. This was run: computing 1000000000 * 1073741824 as a Number gives 1073741824000000000, and Number.isSafeInteger reports false for it, so the low digits are not trustworthy and two distinct keys can compare equal. The reference therefore uses BigInt, with 1000000000n << 30n | 1000000000n giving the exact 1073741825000000000. This is the case the brief's rule is about: more than 31 value bits in JavaScript means BigInt or splitting the value, and here splitting would mean keeping the comparator, which is the thing the problem is avoiding.

In C and C++ the shift must be (long long)a << 30 or the multiplication is done in int and overflows. In Java it must be (long) a << 30 for the same reason.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ a ≤ 1000000000` - `0 ≤ b ≤ 1000000000`