# On the complexity of sock-matching

```When I fold laundry, I pair up matching socks.  Usually I put matching pairs of socks
into the washing machine, then take a lot of individual socks out of the dryer; then,
during folding, I recreate the pairs from a stream of individual socks by the
following method.  I maintain an "unpaired sock buffer", usually on my leg, which is
initially empty.  Then, for each sock in the sequence, I do a sequential search
through this buffer for its mate.  If I find the mate, I remove it from the buffer and
form a pair; if I do not, I add the new sock to the buffer.```
```
When the number of socks remains small, this works well; but it's slow for a large
load of laundry; the average size of the buffer gets larger (I suspect it's
proportional to the total number of socks) and so processing each sock takes longer.
Other possible methods exist; for example, you could limit the sock buffer size and
put overflow socks (either from the sequence or, to guard against stray single socks,
from the sock buffer) into an overflow pile, which you'd process after the initial
sock sequence; or you could sort the sequence into subsequences by some attribute such
as color.

The worst case for this problem is to compare every sock against every other sock.
The worst case for the naive sock-buffer method isn't that bad; it happens when the
sock sequence is palindromic.  Here, you need only compare to half the other socks at
most, and a quarter of them on average, which is four times better than the worst
case.  I wonder if other methods that take into account only equality of socks can do
better.  (Clearly, once you categorize socks by color, size, cut, and other
attributes, you can use any of a variety of O(N lg N) sorting algorithms.  Radix
sorting with a radix around 5-10 seems to work best for me, beating out
comparison-based schemes by a factor of five or so.)
```