Entropy of shuffled sequence split into two groups Let it be a sequence of $N$ elements that can be ordered. At each draw, all elements from the sequence are shuffled. Example with $N = 8$:
$draw_1 = (e_4, e_3, e_0, e_6, e_1, e_7, e_2, e_5)\\
draw_2 = (e_7, e_2, e_0, e_1, e_8, e_3, e_6, e_4)\\
draw_3 = (e_4, e_0, e_3, e_2, e_6, e_5, e_7, e_1)\\
...$
Within a sequence, elements can be pairwise compared. Since there are $N!$ different orderings, each draw has an entropy of $log_2(N!)$ bits.
Now, let's modify the system such that there is two sequences of $N/2$ elements. At each draw, elements are shuffled and half of them goes to the first sequence and the other half to the second sequence. Example with $N=8$:
$
draw_1 = \{(e_4, e_3, e_7, e_0), (e_2, e_1, e_5, e_6)\}\\
draw_2 = \{(e_6, e_3, e_1, e_7), (e_5, e_0, e_2, e_4)\}\\
draw_3 = \{(e_7, e_1, e_5, e_4), (e_0, e_6, e_2, e_3)\}\\
...
$
What is the Shannon entropy of such system if the elements can only be pairwise compared between the two sequence and not within the same sequence? For example, let's define the ordering as $e_n$ < $e_{n+1}$. In $draw1$, $e_4$ is compared to $e_2$, $e_1$, $e_5$ and $e_6$; $e_3$ is compared to $e_2$, $e_1$, $e_5$ and $e_6$ etc. We can use a bit sequence to describe the draw, for example $draw_1=$1100110011110000. I am looking for the entropy of such a sequence.
The full context of this question is described in this crypto.stackexchange question.
 A: Note: I made a logical error, and computed the entropy assuming all microstates were equally likely. Furthermore, I think the approximations I made are a bit too crude to be useful in the range where OP is interested. I leave this answer up since it has some useful ideas, even though it is incomplete and innacurate.

Answer: The entropy of your modified draw sequence has asymptotically the same entropy as the regular draw sequence; both are $\sim \log_2 N!\sim N\log_2 N$.
Let $n=N/2$.
Each draw determines an $n\times n$ binary matrix $M$, where $M_{i,j}=1$ if the $i^{th}$ element of the first sequence is greater than the $j^{th}$ element of the second sequence, and $M_{i,j}=0$ otherwise. You want to count the number of binary matrices you can get.
Define a $2\times 2$ submatrix of $M$ to be the result of selecting two rows of $M$ (not necessarily adjacent) and two columns of $M$, and looking at the four entries of $M$ at the intersection of these rows and columns. Note that our matrix $M$ cannot have any $2\times 2$ submatrices which look like either
$$
\begin{bmatrix}1&0\\0&1\end{bmatrix}
\qquad\text{or}\qquad 
\begin{bmatrix}0&1\\1&0\end{bmatrix}
$$
since this would imply there were entries $a_i,a_j$ in the first sequence and $b_k,b_h$ in the second sequence for which $a_i<b_k<a_j<b_h<a_i$, a contradiction. On the other hand, you can show that every matrix which avoids these submatrices can be constructed from one of your draws. Therefore, counting draws is equivalent to counting matrices avoiding these submatrices.
It turns out that the number of such matrices is
$$
a_n:=\sum_{j=0}^n (j!)^2{n+1\brace j+1}^2
$$
where ${m \brace k}$ is the $(m,k)^{th}$ Stirling number of the second kind, equal to the number of ways to partition a set of size $m$ into $k$ disjoint subsets. For a proof, see the computation following Theorem 2.1 in https://arxiv.org/abs/1103.4884.
The sequence $a_n$ appears in https://oeis.org/A048163, and Vaclav Kotesovec claims $\lim_{n\to\infty}(a_n/n!)^{1/n}/n=C$, where $C=\frac1{e(\log 2)^2}\approx 0.7656928576\dots$ Therefore,
$$
\log a_n\sim \log n! +n\log n+n\log C\tag{$*$}
$$
Using Stirling's approximation, we get that
$$
\log N!\sim N \log N,
$$
while
$$
\require{cancel}
\log a_{N/2}\sim \log (N/2)! + (N/2)\log (N/2)+\cancelto{\approx 0}{\color{gray}{(N/2)\log C}}\sim N\log (N/2)\sim N \log N
$$
That is, both experiments have an asymptotic entropy of $N\log N$, so your restriction with the ordering only mattering between the two halves of the draw has negligible effect on the entropy. I am only keeping track of the dominant terms, but if necessary you can use $(*)$ to get a more precise estimate of the difference between $\log_2 N!$ and $\log_2 a_{N/2}$.
