# $O(n\log n)$ algorithm for minimizing number of inversions in leaves of complete binary tree

I'm having trouble making an algorithm to fit these specs:

• Given a complete binary tree ($$n = 2^d$$ leaves) with integers in leaves.
• Reading the leaves from left to right makes a sequence of integers (we can assume we have an array)

Goal: How can we minimize the number of inversions in that array only by choosing non-leaf nodes and swapping the the subtrees under the given nodes. For example, if the sequence is (4,2,1,3), then choosing the root (swapping its direct children) followed by choosing the right child of the root (and swapping its direct children) turns the sequence into (1,3,2,4), which has only one inversion. This would be the minimum number of inversions.

My approach: My idea was to use something like merge sort but modified. First i would recursively split the array and then when I merge back together I'd need to change the strategy. For the first level of merges (say I have the integers [2] and [1]) I can simply put those in the correct order because our swapping operation doesn't prevent this.

However, once I have to merge something like [1,2] and [3,4] (and larger groups which are powers of 2), I have to move those groups as single units (because of the operation we have to use). I can't put it in exact order like I want but I was thinking maybe it would be best to merge the larger groups by summing up all the numbers inside the groups and moving the groups with the smallest sums to the left to minimize inversions. That seems inefficient though. All the while I have to somehow count inversions. I'm really kind of lost on what to do besides what I've thought of so far. Would anyone be able to help?

Let us denote by $$L(x)$$ the set of leaves in the subtree rooted at $$x$$. The idea is that the decision whether to switch the two children $$x_1,x_2$$ of $$x$$ depends only on $$L(x_1),L(x_2)$$, and depends on how many of the pairs $$(a,b) \in L(x_1) \times L(x_2)$$ satisfy $$a < b$$ and how many satisfy $$b < a$$.
If the sets $$L(x_1),L(x_2)$$ were available to you in their sorted forms, then you could count the number of pairs of each type by merging these sets and doing some accounting. This suggests a recursive algorithm which sorts the leaves using the merge sort strategy.
• 1. Right, I'm saying that you can count inversions on the go. Given the inversions inside $L(x_1)$, the inversions inside $L(x_2)$, and the inversions across $L(x_1),L(x_2)$, the sum gives you the inversions inside $L(x)$. 2. You choose whether to switch or not according to the number of inversions across $L(x_1),L(x_2)$, which you can compute as part of your merge procedure. – Yuval Filmus Feb 10 '19 at 17:28