Advertise here with Carbon Ads

This site is made possible by member support. โค๏ธ

Big thanks to Arcustech for hosting the site and offering amazing tech support.

When you buy through links on kottke.org, I may earn an affiliate commission. Thanks for supporting the site!

kottke.org. home of fine hypertext products since 1998.

๐Ÿ”  ๐Ÿ’€  ๐Ÿ“ธ  ๐Ÿ˜ญ  ๐Ÿ•ณ๏ธ  ๐Ÿค   ๐ŸŽฌ  ๐Ÿฅ”

How to efficiently sort socks

From Stack Overflow, a question about how to efficient sort a pile of socks.

Yesterday I was pairing the socks from the clean laundry, and figured out the way I was doing it is not very efficient. I was doing a naive search โ€” picking one sock and “iterating” the pile in order to find its pair. This requires iterating over n/2 * n/4 = n^2/8 socks on average.

As a computer scientist I was thinking what I could do? sorting (according to size/color/…) of course came into mind to achieve O(NlogN) solution.

And everyone gets it wrong. The correct answer is actually:

1) Throw all your socks out.

2) Go to Uniqlo and buy 15 identical pairs of black socks.

3) When you want to wear socks, pick any two out of the drawer.

4) When you notice your socks are wearing out, goto step 1.

QED