Ways of merging two incomparable sorted lists of elements keeping their relative ordering Suppose that, for a real application, I have ended up with a sorted list A = {$a_1, a_2, ..., a_{|A|}$} of elements of a certain kind (say, Type-A), and another sorted list B = {$b_1, b_2, ..., b_{|B|}$} of elements of a different kind (Type-B), such that Type-A elements are only comparable with Type-A elements, and likewise for Type-B.
At this point I seek to count the following: in how many ways can I merge both lists together, in such a way that the relative ordering of Type-A and Type-B elements, respectively, is preserved? (i.e. that if $P_M(x)$ represents the position of an element of A or B in the merged list, then $P_M(a_i)<P_M(a_j)$ and $P_M(b_i)<P_M(b_j)$ for all $i<j$)
I've tried to figure this out constructively by starting with an empty merged list and inserting elements of A or B one at a time, counting in how many ways each insertion can be done, but since this depends on the placement of previous elements of the same type, I've had little luck so far. I also tried explicitly counting all possibilities for different (small) lengths of A and B, but I've been unable to extract any potential general principle in this way.

For merging N sorted lists, here is a good way to see that the solution is $$\frac{(|A_1|+\dots|+|A_N|)!}{|A_1|!\dots |A_N|!}$$
All the $(|A_1|+\dots|+|A_N|)$ elements can be permuted in $(|A_1|+\dots|+|A_N|)!$ ways. Among these, any solution which has the ordering of the $A_1$ elements different from the given order have to be thrown out. If you keep the positions of everyone except $A_1$ fixed, you can generate $|A_1|!$ permutations by shuffling $A_1$. Only 1 among these $|A_1|!$ solutions is valid. Hence the number solutions containing the right order of $A_1$ is $$\frac{(|A_1|+\dots|+|A_N|)!}{|A_1|!}$$
Now repeat the argument for $A_2$, $A_2, \dots A_N$.
