My answer is not fully algorithmic yet "efficient" when I do it : step 1) discard all your existing socks step 2) go to walmart and buy them by packets of 10

My answer is not fully algorithmic yet "efficient" when I do it : step 1) discard all your existing socks step 2) go to walmart and buy them by packets of 10 - n packet of white and m packets of black. No need for other colors in everyday's life. Yet times to times I have to do this again (lost socks, damaged socks etc.) and I hate to discard perfectly good socks too often (and I wished they kept selling the same socks reference!) so I recently took a different approach. Consider than if you draw only 1 sock for the 2n stack of socks, your odds of finding the matching sock in a naive search is quite low. Pick up 5 of them at random (usually humans are good are remembering between 4 and 7 different elements in the working memory - a bit like the human equivalent of a RPN stack - 5 is a safe default) and memorize their shape or their length. Pick up one from the stack of 2n-5. Now look for a match (visual pattern matching - humans are good at that with a small stack) inside the 5 you drew, if you don't find one, then add that to your 5 and keep randomly picking socks from the stack and compare to your 5+1 socks for a match (it will reduce your performances but raise your odds) Much faster. Feel free to write down the formula (it's late, I'm getting sleepy) to calculate how much samples you have to draw for a 50% odds of a match. IIRC it's an hypergeometric law. I do that every morning and rarely need more than 3 draws. Now you can estimate the size of my stack of stocks :-) BTW I found that the transaction costs of sorting all the socks every time I needed a pair were far less than doing it once and binding the socks - because then you don't have to bind the socks, and there's also a diminishing marginal return (ie you keep looking for that 2 or 3 socks that when somewhere in the laundry and that you need to finish matching your socks and you lose time on that)