Consider the following problem:

Input: two arrays $A$ and $B$ of length $n$.

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

What is the fastest deterministic algorithm for this problem?
Can be it solved faster than sorting them ($O(n \lg n))$?
Can this problem be solved in deterministic linear time?