by forwardslash

Yesterday I was pairing the socks from the clean laundry, and figured out the way I was doing it is not very efficient. I was doing a naive search - picking one sock and "iterating" the pile in order to find its pair. This requires iterating over n/2 * n/4 = n2/8 socks on average.

As a computer scientist I was thinking what I could do? sorting (according to size/color/...) of course came into mind to achieve O(NlogN) solution.

Hashing or other not in-place solutions are not an option, because I am not able to duplicate my socks, (though it could be nice if I could).

So, the question is basically:

Given a pile of n pairs of socks, containing 2n elements (assume each sock has exactly one matching pair), what is the best way to pair them up efficiently with up to logarithmic extra space (I believe I can remember that amount of info if needed)

Interesting and fun question which is of course closed by stackoverflow.