This is what I do: lay them out and pair them as the layout continues. O(n) to pair n socks, but that's cheating a bit because you can see them all at a glance.

This is what I do: lay them out and pair them as the layout continues. O(n) to pair n socks, but that's cheating a bit because you can see them all at a glance. Particularly works well with my daughter's socks, the little ones are really hard to keep track of. I have an O(1) solution that is fairly reliable for matching a single pair. Pick out a sock from the drawer. Then go find your kids; they ran off with the matching one when you weren't looking (requires that you live with at least one young child).