There are $n$ pairs of socks, all different. They all went out of the dryer, so there are now $2n$ socks scattered around. Given two socks, the only operation I can do is to decide whether they are identical (- belong to the same pair) or different (- belong to different pairs). What is the best way to sort the socks in matching pairs?
The obvious algorithm is: grab a sock, scan the pile for its matching sock, and put that pair aside. This algorithm requires time $O(n^2)$.
I Found a related question, On the complexity of sock-matching from about 10 years ago, which also describes an $O(n^2)$ algorithm.
If each sock has a numeric ID, or another ordinal property, such as: wavelength of color, then the entire set of socks can be sorted by that ordinal property in time $O(n log n)$, and then the pairs can just be collected with an $O(n)$ scan. But, in this question I assume that there is no order on the socks - we can only tell whether two socks are identical or different.
In a similar question in StackOverflow (How to pair socks from a pile efficiently?), the accepted answer suggests to use a hash, but again, this assumes that each sock can be represented by a set of properties such as color, pattern, etc., so that each property can be handled separately. In this question I assume that the properties of the socks are only accessible via a function that tells whether two socks are identical or different.
There is a paper named Sock sorting, which initially seems related, but actually it deals with another problem, where two socks might seem identical although they are different (this probably makes the problem more difficult).
So, my question is: assuming we only have a binary "identical/different" relation on the socks, can we match the socks faster than $O(n^2)$?
