From Jason Kottke’s kottke.org

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 = n^{2}/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 an 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.)

I will appreciate an answer that addresses the following aspects:

- A general
*theoretical*solution for a huge number of socks. - The actual number of socks is not that large, I don’t believe me and my spouse have more than 30 pairs. (And it is fairly easy to distinguish between my socks and hers, can this be utilized as well?)
- Is it equivalent to the element distinctness problem?

**One option:**

*Suppose that you know that your 2n socks are arranged this way:*

*p _{1} p_{2} p_{3} … p_{n} p_{f(1)} p_{f(2)} … p_{f(n)}*

*where f is an unknown permutation of the set {1,2,…,n}. Knowing this cannot make the problem harder. There are n! possible outputs (matchings between first and second half), which means you need log(n!) = Omega(n log n) comparisons. This is obtainable by sorting.*

*Since you are interested in connections to element distinctness problem: proving the Omega(n log n) bound for element distinctness is harder, because the output is binary yes/no. Here, the output has to be a matching and the number of possible outputs suffices to get a decent bound. However, there’s a variant connected to element distinctness. Suppose you are given 2n socks and wonder if they can be uniquely paired. You can get a reduction from ED by sending (a _{1}, a_{2}, …, a_{n}) to (a_{1}, a_{1}, a_{2}, a_{2}, …, a_{n}, a_{n}). (Parenthetically, the proof of hardness of ED is very interesting, via topology.)*

*I think that there should be an Omega(n ^{2}) bound for the original problem if you allow equality tests only. My intuition is: Consider a graph where you add an edge after a test, and argue that if the graph is not dense the output is not uniquely determined.*

**Another option**

```
List<Sock> UnSearchedSocks = getAllSocks();
List<Sock> UnMatchedSocks = new list<Sock>();
List<PairOfSocks> PairedSocks = new list<PairOfSocks>();
foreach (Sock newSock in UnsearchedSocks)
{
Sock MatchedSock = null;
foreach(Sock UnmatchedSock in UnmatchedSocks)
{
if (UnmatchedSock.isPairOf(newSock))
{
MatchedSock = UnmatchedSock;
break;
}
}
if (MatchSock != null)
{
PairedSocks.Add(new PairOfSocks(MatchSock, NewSock));
UnmatchedSocks.remove(MatchedSock);
}
else
{
UnmatchedSocks.Add(NewSock);
}
}
```

**The right answer**

*1) Throw all your socks out.*

*2) Go to Uniqlo and buy 15 identical pairs of black socks.*

*3) When you want to wear socks, pick any two out of the drawer.*

*4) When you notice your socks are wearing out, goto step 1.*

Buying 15 identical pairs would be boring! Certainly not the wardrobe of a swinger!