How can I pair socks from a pile efficiently?

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.

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?

• Use sorting. The theoretical limit is O(n) because you need to touch each sock (unless some are already paired somehow). You can achieve O(n) with radix sort. You just need to pick some attributes for the buckets.
  1. First you can choose (hers, mine) – split them into 2 piles,
  2. then use colors (can have any order for the colors, e.g. alphabetically by color name) – split them into piles by color (remember to keep the initial order from step 1 for all socks in the same pile),
  3. then length of the sock,
  4. then texture
  5. And so on…

  If you can pick a limited number of attributes, but enough attributes that can uniquely identify each pair, you should be done in O(k * n), which is O(n) if we can consider k is limited.

• As the architecture of the human brain is completely different than a modern CPU humans can win over CPU algorithms using the fact that “finding a matching pair” can be one operation (Single instruction, multiple data (SIMD)) for a set that isn’t too big.

  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);
  }

• Sorting is a little too much. We don’t need order; we just need equality groups. So hashing would be enough (and faster).
  1. For each color of socks, form a pile. Iterate over all socks in your input basket and distribute them onto the color piles.
  2. Iterate over each pile and distribute it by some other metric (e.g. pattern) into the second set of piles
  3. Recursively apply this scheme until you have distributed all socks onto very small piles that you can visually process immediately