Deterministic linear time algorithm to check if one array is a sorted version of the other

Consider the following problem:

Input: two arrays $A$ and $B$ of length $n$, where $B$ is in sorted order.

Query: do $A$ and $B$ contain the same items (with their multiplicity)?

What is the fastest deterministic algorithm for this problem?

Can it be solved faster than sorting them?
Can this problem be solved in deterministic linear time?

You haven't specified your computation model, so I will assume the comparison model.

Consider the special case in which the array $B$ is taken from the list
$$
\{1,2\} \times \{3,4\} \times \cdots \times \{2n-1,2n\}.
$$
In words, the $i$th element is either $2i-1$ or $2i$.

I claim that if the algorithm concludes that $A$ and $B$ contain the same elements, that the algorithm has compared each element in $B$ to its counterpart in $A$. Indeed, suppose that the algorithm concludes that $A$ and $B$ contain the same elements, but never compares the first element of $B$ to its counterpart in $A$. If we switch the first element then the algorithm would proceed in exactly the same way, even though the answer is different. This shows that the algorithm must compare the first element (and any other element) to its counterpart in $A$.

This means that if $A$ and $B$ contain the same elements, then after verifying this the algorithm knows the sorted order of $A$. Hence it must have at least $n!$ different leaves, and so it takes time $\Omega(n\log n)$.

StackExchange Computer Science Q#51462, answer score: 14