Detecting duplicates in an array using divide and conquer

You can't check for duplicates in O(nlogn) if you can't order the items, and you can't order them if you can only compare for equality.

In fact, you can't be sure there are no duplicates unless you compare every pair, and there are n(n-1)/2 such pairs.