Complexity to insert subset of array to minimize order inversions
Since this problem is basically about merging the element not in $B$ with element in $B$ to minimize order inversions, this answer will be focused on the following problem. The algorithm and analysis hereof can be extended to the problem in the question easily.

$A$ is a sorted array of $n$ integers. $B$ is an array of $m$ integers. $n\gt0, m\gt0$.
How can we merge them into one array efficiently without changing the order of elements in $B$ so that the result array has minimum number of inversions?   


As OP indicated, the problem above can be done trivially in $O(nm)$. &quot;For each element in $A$ you scan through $B$ and compute the number of inversions that would happen if inserting there, and simply put the element in the gap that minimizes it.&quot;  The OP also noted that in the result array, we should keep elements that come from $A$ sorted. 
The observations above given by OP lead to the following recursive helper algorithm that gives the indices where elements of $A$ should be inserted into $B$. The simple idea is &quot;binary insertion&quot;. That is, insert the middle element into $B$, then recurse.
Pythonic notations will be used.
Input: $A$ is an array with $A[sa\colon ea]$ sorted. $B$ is another array with subarray $B[sb\colon eb]$ specified. $I$ is an array of the same length as $A$.
Output: updated $I$, such that if for each element $A[i]$ in $A[sa\colon ea]$, we insert $A[i]$ right before $B[I[i]]$, keeping the original order of $A$ among themself, the inversion number of $A[sa\colon ea]$ merged with $B[sb\colon eb]$ is minimized.
Procedure:

If $sa\ge ea$, return.
Let $ma = (sa + ea)//2$
Scan through $B[sb\colon eb]$ to find the indice $mb$ in range($sb\colon eb+1$) such that if we put $A[ma]$ right before $B[mb]$, we will have minimum number of inversions that consist of $A[ma]$ and an element in $B[sb\colon eb]$.  (Or, any one of those optimal indices). 
Let $I[ma] = mb$.
Call this procedure with $A[sa\colon ma-1]$, $B[sb\colon mb]$ and $I$.
Call this procedure with $A[ma+1\colon sb]$, $B[mb\colon eb]$ and $I$.

To solve the initial problem, we will do the following.

Initialize $I$, an array of $n$.
Run the algorithm above with $A[0\colon n]$, $B[0\colon m]$ and $I$
Merge $A$ with $B$ according to $I$.
Return the merged array.


If implemented properly, the algorithm above runs in $O(m\log n + n\log m)$ time. It can be proved that $O(m\log n + n\log m)$ time is optimal. It uses $O(n)$ auxiliary space.
The algorithm here is, basically, doing the same thing to find the same arrangement as in OP's pesudocode. Only more efficiently.
It is a nice exercise to prove the correctness of either algorithm. 

If the given array $A$ is not sorted, then sort it at the start of the algorithm. That will add $O(n\log n)$ to its time-complexity.