‘How to Pair Socks From a Pile Efficiently?’

Amit on Stack Overflow asks:

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?

What a great question and the answers don’t disappoint. Of course the easiest way to do this is just to buy all of the same socks — or just a few different socks so that there are fewer variables — but that would be no fun.

Speaking of socks, you guys know what you should be matching your socks with right?

Personally I try for socks that have a base color that matches my pants of the day with an accent color that either matches something else I am wearing, or just adds some life to a boring color palette that I may be wearing that day.

Originally posted for members on: January 21, 2013
Follow along on RSS, App.net, or Twitter.
~I would appreciate it if you considered becoming a member.~