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][1] algorithm for this problem?  
Can it be solved faster than sorting them ($O(n \lg n)$ time, or $O(n \lg\lg n)$ (see Yuval's comment))?
Can this problem be solved in deterministic linear time?

The answers below conclusively answer this question for many popular models, but not the one I'm looking for: the Turing machine model.

  [1]: https://en.wikipedia.org/wiki/Deterministic_algorithm