Proof of membership and non-membership in Merkle tree (Hash-tree)
If you don't use a merkle tree then checking membership is an O(n) operation, as opposed to O(log n) with a merkle tree. Instead of going through each item in the set, you walk up one branch of the merkle tree which has O(log n) depth.
Though, without sorting, proving non-membership still requires O(n) steps. Sorting makes it possible to prove non-membership by only looking at the leaf nodes that would be adjacent to the non-element.
I found this short summary here that's really useful.