Efficiently inserting into list keeping number of inversions minimal

Question

Assume two lists of comparable items: u and s. Let INV(u) be the number of inversions in u.

I am looking for an efficient algorithm to insert the items of s into u with a minimal increase of INV(u).

Basically I would like to insert objects into a list while keeping it "as sorted as possible" while keeping the order of the first list.

Example:

u = [4,6,2,9,7]
INV(u) = 3 ((4, 2), (6, 2) and (9, 7)

s = [8,3,10]

one optimal solution u' = [3, 4, 6, 2, 8, 9, 7, 10]
INV(u') = 5 ((4, 2), (7, 2) and (9, 7) + (3,2), (8,7))

different optimal solution u' = [3, 4, 6, 2, 9, 7, 8, 10]
INV(u') = 5 ((4, 2), (7, 2) and (9, 7) + (3,2), (9,8))

As you can see there is no unique optimal solution.

I'd be glad for any sort of ideas or direction to look into.

Answer 1

This is an elaboration on on trevore's answer. It's too long to fit in a comment and contains the proofs of his solution (or at least how I understand it).

You can show that in any optimal solution, the elements of $s$ will appear ordered. If not, assume $s_1 < s_2$ and they appear in reverse order in an optimal solution. Let $\sigma_1$ be the number of elements between $s_1$ and $s_2$ that are less than $s_1$ and $\beta_1$ be the number of those that are bigger than $s_1$. Define $\sigma_2$ and $\beta_2$ similarly for $s_2$. Note that $\sigma_1 \leq \sigma_2$ and $\beta_2 \leq \beta_1$. Swapping $s_1$ and $s_2$ will change the number of inversions by $-\beta_1 + \beta_2 - \sigma_2 + \sigma_1 - 1$ which is at most -1.

It is not hard to see that elements of $s$ can be inserted independently. Since they appear ordered, the elements of $s$ do not "feel" each other's presence. That is, pairs of elements from $s$ do not contribute to the inversion count. To do that, insert the median of $s$ optimally in linear time. Then, recursively, insert elements of $s$ less than the median to the left of the median and elements bigger than the median to its right.

Let the median be inserted in position $k$, the runtime of this satisfies, $T(|s|, |u|) = T(|s| / 2, |u| - k) + T(|s| / 2, k) + |u| + |s|$, the linear $|s|$ factor is for finding the median and shuffling the elements of $s$. It is easy to show by induction that $T(|s|, |u|) = O(|s| \log |s| + |u| \log |s|)$.

Note that the dependence on $|s|$ here is optimal. Since solving the problem with empty $u$ is equivalent to sorting $s$ using only comparisons. The dependence on $|u|$ is also optimal, since the problem for a singleton list $s$ and a list $u$ must require linear work.

Answer 2

Ok, here is my solution:

An observation (which I more or less proved) is that an optimal solution will always be one in which s is sorted ascendingly. This gives rise to an O((|u|+|s|)*log(|s|)) algorithm.

To find the optimal solution for a single element, do as I said in my comment: Take one element from s, compare it to each element in u from left to right, increment a counter is an inversion and carry the previously calculated number over. Then traverse the list from right to left with the same element, increasing the counts for each position.

This is O(|u|).

Sort s.

For the middle element of s at position m: Find the best position b in u (using the method from above).

Split s at m and u at b and recursively call with the left and the right parts, concatenating the results with m in the right order.

Stop as soon as u or s are empty.