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?
This urgent plea received 33 answers that look into the depths of the sock-pairing quandary. One answer suggests using recursive hash partitioning, which is actually used by the Microsoft database management system SQL Server. In the case of the mismatched socks, you would make a pile for each color of socks. Then you would divvy that up by pattern or another metric, and recursively apply until you're left with two socks in each pile. The same engineer suggests another solution: parallelism (or getting your friends to help you out).
One eager Stack Overflow user commented on this answer: "This is exactly what I do! I make piles dependent on the style of the opening of the sock." And this enthusiasm is carried throughout the lengthy discussion.
Another gem of an answer actually puts his process of sock-pairing into code:
spread_all_socks_on_flat_surface();
while (socks_left_on_a_surface()) {
// thanks to human visual SIMD, this is one, quick operation
pair = notice_any_matching_pair();
remove_socks_pair_from_surface(pair);
}
Others suggest non-algorithmic solutions like throwing out all of your socks and purchasing identical socks to avoid the problem entirely. For more valuable insights on how to best pair your socks, check out the full question and answer.
And ladies and gentlemen, there you have it. A computer scientist's guide to taking one sock and finding its companion.