# 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.

• Food for thought: The naive approach would be: Take one element from s, compare it to each element in u from left to right, increment if it 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 runs in O(|s|*|u|) with space = O(|u|) – trevore Apr 15 '16 at 6:54
• Inspecting all maximal increasing subsequences may lead somewhere. – Raphael May 25 '16 at 15:57

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.

• Thanks for elaborating. That is exactly the solution I meant. – trevore Dec 12 '16 at 12:11

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.

• I don't understand this. s is an input. You can't assume s is in sorted order. Your algorithm must work for all possible values of s. – D.W. Aug 10 '16 at 14:25
• Yes, but in any optimal solution the elements of s will always end up being sorted ascendingly in the new array. Note the step "Sort s." See the example above. What I proved so far is that: for a, b in s, a<b if a is optimally placed in u, then the optimal place for b is to the right of a. – trevore Aug 11 '16 at 9:18