https://stackoverflow.com/questions/14415881/how-to-pair-socks-from-a-pile-efficiently

Особенно понравилось:

Case 1: All socks are identical (this is what I do in real life by the way).

Pick any two of them to make a pair. Constant time.