This is how I actually do it, for p pairs of socks (n = 2p individual socks):

• Grab a sock at random from the pile.
• For the first sock, or if all previously-chosen socks have been paired, simply place the sock into the first "slot" of an "array" of unpaired socks in front of you.
• If you have one or more selected unpaired socks, check your current sock against all the unpaired socks in the array.
• It is possible to separate socks into general classes or types (white/black, ankle/crew, athletic/dress) when building your array, and "drill-down" to only compare like-for-like.
• If you find an acceptable match, put both socks together and remove them from the array.
• If you do not, put the current sock into the first open slot in the array.
• Repeat with every sock.

The worst-case scenario of this scheme is that every pair of socks is different enough that it must be matched exactly, and that the first n/2 socks you pick are all different. This is your O(n²) scenario. However, if the number of unique types of sock t is less than the number of pairs p = n/2, and the socks in each type are alike enough (usually in wear-related terms) that any sock of that type can be paired with any other, then as I inferred above, the maximum number of socks you will ever have to compare to is t, after which the next one you pull will match one of the unpaired socks. This scenario is much more likely in the average sock drawer than the worst-case, and reduces the worst-case complexity to O(n*t) where usually t << n.

This is how I actually do it, for p pairs of socks (n = 2p individual socks):

• Grab a sock at random from the pile.
• For the first sock, or if all previously-chosen socks have been paired, simply place the sock into the first "slot" of an "array" of unpaired socks in front of you.
• If you have one or more selected unpaired socks, check your current sock against all the unpaired socks in the array.
• It is possible to separate socks into general classes or types (white/black, ankle/crew, athletic/dress) when building your array, and "drill-down" to only compare like-for-like.
• If you find an acceptable match, put both socks together and remove them from the array.
• If you do not, put the current sock into the first open slot in the array.
• Repeat with every sock.

The worst-case scenario of this scheme is that every pair of socks is different enough that it must be matched exactly, and that the first n/2 socks you pick are all different. This is your O(n²) scenario, and it's extremely unlikely. If the number of unique types of sock t is less than the number of pairs p = n/2, and the socks in each type are alike enough (usually in wear-related terms) that any sock of that type can be paired with any other, then as I inferred above, the maximum number of socks you will ever have to compare to is t, after which the next one you pull will match one of the unpaired socks. This scenario is much more likely in the average sock drawer than the worst-case, and reduces the worst-case complexity to O(n*t) where usually t << n.