Number of adjacent swaps

Question

Given an initial sequence of $n$ integers $(1,2,\ldots,n)$ and an ending sequence (which is a permutation of those $n$ integers), what is the minimum number of adjacent swaps involving the $n/2$ integers? (Assume $n \geq 2$ is a power of $2$). Note that the operation to get the final sequence is only by adjacent swaps.

For example when $n = 4$, if the ending sequence is $(4,3,1,2)$, then there have been a minimum of $3$ adjacent swaps involving the first $4/2 = 2$ integers.
Since we go
$(1,2,3,4) \rightarrow(1,2,4,3)$ ($4$ swaps with $3$, but the count is $0$ since we consider the first $4/2 = 2$ integers
$(1,2,4,3)\rightarrow (1,4,2,3)$ ($4$ swaps with $2$, and count is now $1$, since $4$ was in the first $2$ integers)
$(1,4,2,3) \rightarrow(4,1,2,3)$ ($4$ swaps with $1$, and count is now $2$, since $1$ is in the first $2$ integers)
$(4,1,2,3)\rightarrow(4,1,3,2)$ ($3$ swaps with $2$ but count is still $2$)
$(4,1,3,2) \rightarrow (4,3,1,2)$ ($3$ swaps with $1$ and count is incremented to $3$).

Let me know if any clarification is needed!

I've tried doing some recursion since it involves only the first $n/2$ integers, but no ideas from there. I thought I could use some combinatorial argument too but it gets messy when I test with $n\geq 8$.

Response to possible duplicate: I think mine is different. Mine only counts the number of operations in the first $n/2$ integers, whereas that gives a method for the entire string of integers. I'm having trouble finding a formula or function for the number of minimum operations.

Answer 1

It is different from previous question, but answer is similar: call "wrongness" of permutation the number of pairs of elements in wrong order in the first half multiplied by $2$, plus number of pairs (element from the first half, element from the second half).

If wrongness is zero (so the first half is already as we want it to be), we need to just rearrange second half, and we don't need any swaps in the first half to do it.

If wrongness is not zero, we can always decrease it by either $1$ swapping the $n/2$-th and the $n/2+1$ elements, or by $2$ by swapping some elements in the first half. Indeed, take some $p_i$ in the first half and $p_j$ s.t. $i < j$ but $p_i$ should be in the right of $p_j$. There is some adjacent out-of-order pair in $p_i, p_{i + 1}, \ldots, p_j$. If this pair intersects first half - we can swap this elements, reduce wrongness by $1$ or $2$ and pay $1$ or $2$ correspondingly. If both elements are in the second part - swap them (and pay nothing). As it decreases number of out-of-order pairs in the second part, we will eventually get a pair that intersects the first part.

So wrongness is upper bound on number of swaps we need. It's easy to see that any operation decreases wrongness by at most amount of swaps in the first half, so it's also lower bound.

Answer 2

It is easier to do the process in reverse - start with the mixed arrangement and sort them. As any sequence of swaps is invertible, this takes the same number of swaps.

You can sort the numbers using the following 4 stage process:

1. Sort the numbers in the right half. This costs nothing.
2. Move the small numbers to the left half, without changing their relative order. This also moves the large numbers to the right half without changing their relative order.
3. Sort the small numbers in the left half.
4. Sort the large numbers in the right half. This costs nothing.

In stage 2, every swap shifts a large number that lies directly to the left of a small number one place to the right. Any swaps involving that large number after it reaches the right half don't count. So the number of swaps that we need is equal to the total distance that any large numbers in the left half need to reach past the midpoint. This is not affected by stage 1, so can be counted at the start.

In stage 3, every swap exchanges two small numbers that are out of order. To get the number of swaps needed, simply count the number of pairs of small numbers (adjacent or not) that are out of order. This is affected by stage 1, because any two small numbers that both start in the right half will have been sorted then. Stage 2 does not affect their relative order. So we only need to count pairs of small numbers that are out of order and not both in the right half.

To recap, let's define the wrongness as sum of all the following:

• the distance from any large number in the left half to the middle. If we number the locations from $1$ to $n$, any large number in location $k\le n/2$ contributes $n/2+1-k$ to the wrongness.
• the number of out-of-order small number pairs that are not both in the right half.

The number of swaps needed that involve at least one of the left half locations is equal to this wrongness. Using the 4 stages above to sort them attains this number of swaps, and it is fairly easy to see that at least this number of swaps is necessary.

Example: $(4,2,6,3,5,1)$: We need $3+1$ swaps to get items 4 and 6 to the right, and $1$ more because of the $(2,1)$ pair of small numbers. Note the small pair $(3,1)$ does not count as they both lie in the right half. So the wrongness is $5$.

And here it is:
$(4,2,6,3,5,1)$
Stage 1 is free:
$(4,2,6,1,3,5)$
Stage 2 uses 4 swaps that count:
swap 1: $(4,2,1,6,3,5)$
free : $(4,2,1,3,6,5)$
swap 2: $(2,4,1,3,6,5)$
swap 3: $(2,1,4,3,6,5)$
swap 4: $(2,1,3,4,6,5)$
Stage 3:
swap 5: $(1,2,3,4,6,5)$
Stage 4:
free : $(1,2,3,4,5,6)$