Detecting duplicates in an array using divide and conquer

Question

I was given the following question on an exam and it seems as though it might not be possible. Is there something I'm missing?

Given an array of n objects which can be compared only for equality, and knowing nothing about the range of values in the array, give a divide and conquer solution for detecting the existence of any duplicates in the array. This must be an O(nlogn) solution.

We can safely assume due to the nature of the question that the solution likely has nothing to do with data structures or radix sorts, so can this be done in-place?

If so, how?

Answer 1

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.