Skewed Sorting

Farmer John has $2^N$ cows ($1 \le N \le 10$), each branded on her flank with a distinct integer label in the range $1 \dots 2^N$. They stand in a line in some arbitrary order: the first cow is $\mathrm{cow}_1$, the second is $\mathrm{cow}_2$, and so on.

He reorders them with the following recursive procedure:

1. If the current line holds more than one cow, split it into two halves of equal length. First apply this same procedure to the left half, then apply it to the right half.
2. Treat the two resulting halves as two equal-length numbers written in base $2^N$, one cow per digit with the most significant digit on the left. If the second (right) number is smaller than the first (left) number, swap the two halves: the cow at each offset of the left half exchanges places with the cow at the same offset of the right half.

Because every label is distinct, the two halves can never be equal, so this comparison always resolves.

Every time two halves of length $k$ are swapped, all $2k$ cows involved move exactly $k$ positions, so that swap adds $2k^2$ to the running total distance.

Run the procedure on the initial line, then report the total distance travelled by all cows together with the final order of the line.

As an example, consider this line of $2^3 = 8$ cows:

8 5 2 3 4 7 1 6

First John sorts each half separately:

8 5 2 3 | 4 7 1 6

Each half still holds more than one cow, so it is split again. Starting with the left half:

8 5 | 2 3

Splitting once more gives

8 | 5      and      2 | 3

each of which is handled by rule 2, ultimately yielding

5 | 8      and      2 | 3   (unchanged)

Turning 8 5 into 5 8 moves each of the two cows one position, so the total distance becomes $2$. The pair 2 3 was already ordered, so the total stays at $2$. The left group now reads

5 8 | 2 3

Applying rule 2 to 5 8 versus 2 3: since 2 precedes 5, we swap the two pairs:

2 3 5 8

Each of these four cows moved two positions, adding $8$, so the total becomes $10$.

Now the right group 4 7 | 1 6 splits into 4 7 and 1 6, both already ordered. Comparing them, 1 precedes 4, so we swap:

1 6 4 7

adding another $8$ and bringing the total to $18$.

The line now looks like this, ready for the final application of rule 2 to the two groups of four:

2 3 5 8 | 1 6 4 7

Since 1 precedes 2, we swap the halves:

1 6 4 7 2 3 5 8

Each of the eight cows moved four positions, adding $32$ and making the total $50$.

So the answer is a distance of $50$ and the final line 1 6 4 7 2 3 5 8.

• Line 1: a single integer $N$.
• Lines 2 to $2^N + 1$: line $i + 1$ contains a single integer, the label of $\mathrm{cow}_i$.

• Line 1: a single integer, the total distance travelled by all the cows.
• Lines 2 to $2^N + 1$: line $i + 1$ contains a single integer, the $i$-th cow in the final line.