When you get the socks, attach a pair identifier to each sock in the pair. The ids start at 0 and increment by one for each new pair. When a sock is lost, disc

When you get the socks, attach a pair identifier to each sock in the pair. The ids start at 0 and increment by one for each new pair. When a sock is lost, discard it's peer. When the pair is replaced, reuse the id. This keeps the ids dense. After doing the laundry, you can place each sock based on its id, and match up everything in O(n). Washing them paired up (one rolled inside the other) is even better, O(n), where n is the number of pairs, not the number of socks. But I don't think the socks get really clean.