Intuitively I'd say a human pairing socks is far better than O(n2) because finding something that matches a given sock is close to O(1) on small sets.
Of course, there's an enlightening stackoverflow question on this: http://stackoverflow.com/q/14415881/220347
Finally, my graduate-level algorithms class comes in handy in real life.
Why not do a O(1) Pair folloed by an O(1) Search.