When I sort socks, I do an approximate radix sort, dropping socks near other socks of the same colour/pattern type. Except in the case when I can see an exact match at/near the location I'm about to drop the sock I extract the pair at that point.
Almost all the other algorithms (including the top scoring answer by usr) sort, then remove pairs. I find that, as a human, it is better to minimize the number of socks being considered at one time.
I do this by:
- Picking a distinctive sock (whatever catches my eye first in the pile).
- Starting a radix sort from that conceptual location by pulling socks from the pile based on similarity to that one.
- Place the new sock near into the current pile, with a distance based on how different it is. If you find yourself putting the sock on top of another because it is identical, form the pair there, and remove them. This means that future comparisons take less effort to find the correct place.
This takes advantage of the human ability to fuzzy-match in O(1) time, which is somewhat equivalent to the establishment of a hash-map on a computing device.
By pulling the distinctive socks first, you leave space to "zoom" in on the features which are less distinctive, to begin with.
After eliminating the fluro coloured, the socks with stripes, and the three pairs of long socks, you might end up with mostly white socks roughly sorted by how worn they are.
At some point, the differences between socks are small enough that other people won't notice the difference, and any further matching effort is not needed.