1055. Arranging the Pieces Into One Number

n non-negative integers are given. Write them one after another, in any order you choose, to form a single long number. Print the LARGEST number obtainable.

3 30 34 5 -> 534330 10 2 -> 210 121 12 -> 12121 0 0 0 -> 0

Every piece must be used exactly once, and the pieces are written exactly as given, so 30 contributes the two characters 3 and 0.

## What most people try first

Sort the numbers descending. That gives 34 30 5 3 for the first sample, spelling 3430 5 3 which reads 3430 53, that is 343053, and the real answer is 534330. Numerical order is not the right order because the pieces have different LENGTHS: 5 beats 34 as a leading piece even though 5 < 34.

Sorting by the first digit is closer and still wrong: 3 and 30 and 34 all start with 3, and 3 must come before 30 (330 beats 303) while 34 must come before 3 (343 beats 334).

Trying every order is n!, which is the brute force this was checked against for n <= 7.

## Compare by what the pair spells

Sort with the comparator

x comes before y when x followed by y > y followed by x

comparing those two concatenations as STRINGS of equal length. Then write the sorted pieces out.

On 3 and 30: 330 versus 303, so 3 first. On 34 and 3: 343 versus 334, so 34 first. On 5 and 34: 534 versus 345, so 5 first. The sorted order is 5 34 3 30, spelling 534330.

## Why a pairwise rule decides a global order

Two facts are needed, and skipping either is where this problem is usually got wrong.

FIRST, the comparator is a valid ORDER. It is total and antisymmetric by construction, and it is transitive: if x+y >= y+x and y+z >= z+y then x+z >= z+x. The quickest way to see it is to note that x + y > y + x is exactly the statement that

value(x) / (10^len(x) - 1) > value(y) / (10^len(y) - 1)

which is a comparison of two real numbers, and real numbers are transitive. That identity comes from writing the infinite repetition of x as a geometric series. Without transitivity the sort is not even well defined, and different sorting algorithms would give different answers.

SECOND, sorted order is OPTIMAL, by an exchange argument. Take any arrangement that is not sorted. It has two ADJACENT pieces y, x with x ordered before y. Everything outside that pair is unchanged when they are swapped, and the swap replaces the substring y+x with x+y, which is larger. Both results have the same total length, so larger substring at the same position means larger number. Repeating the swap sorts the arrangement while never decreasing it.

Adjacent swaps are what make this work. A pairwise comparator says nothing directly about pieces that are far apart, and it does not have to, because every permutation is reachable by adjacent swaps.

## The all-zeros case

0 0 0 spells 000, which must print as 0. This is the only case where the naive concatenation has a leading zero, because any non-zero piece sorts ahead of every zero.

## Overflow

The result has up to 1000 * 10 = 10000 digits and is never held as an integer. Everything is string work, and the comparator compares strings. Trying to compute it numerically is the mistake this problem is really testing for.

## Where this sits

Problem #841 DELETES digits from one number to make the largest result and keeps the surviving digits in order. This one REARRANGES whole pieces and deletes nothing. Both are greedy on "what goes furthest left", and the arguments are different: #841's is about a fixed-length result, this one's is about a comparator being an order.

## Cost

Time O(n log n) comparisons, each costing the length of the two pieces. Space O(n).

Constraints - `1 ≤ n ≤ 1000` - `0 ≤ a[i] ≤ 1000000000` - each piece is written with no leading zeros