Consider $ab$ and $cd$ which are two words. We merge these two into 6 possibilities: $abcd, acbd, acdb, cabd, cadb, cdab$
So in general, a merge of words/sequences $x, y ∈ Σ∗$ , is a word of length $|x| + |y|$ with both $x$ and $y$ as disjoint subsequences in it.
For two languages $L1$ and $L2$ their merge is defined as the set of all possible merges of two words $x ∈ L1, y ∈ L2$.
So basically, a merge is a modified shuffle and should be of length that of the sum of the length of two languages, and should also be in order (see $ab$ and $cd$ example, as $b$ could not come before $a$).
I was thinking of just connecting the states of all $L1$ and $L2$ but this seems wrong as if you connect them all like a fully connected graph, one can jump and go back which is not acceptable.
What's a basic idea on the construction I could do to prove this?
The idea is to construct a new NFA $A$ so that every state of $A$ contains a state of $L_1$ and a state of $L_2$. When you read a letter, you nondeterministically choose to advance either $L_1$ or $L_2$.