Efficiently inserting into list keeping number of inversions minimal

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.

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.

StackExchange Computer Science Q#55862, answer score: 2