sock matching algorithm
A comparison with a result "different" doesn't add information regarding any other sock in the pile (If sock B didn't match A, and Sock C didn't match A, the chance of B and C  to be a match is still the same as with any other sock). therefor no sorting or organization can be made, rather then knowing for each sock which socks don't match it based on this comparison. this leads back to the naive algorithm, which is $O(n^2)$.

Pretty disappointing...