title: How can I pair socks from a pile efficiently?
body: <p>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&nbsp;— picking one sock and "iterating" the pile in order to find its pair. This requires iterating over n/2 * n/4 = n<sup>2</sup>/8 socks on average.</p>
  
  <p>As a computer scientist I was thinking what I could do? Sorting (according to size/color/...) of course came to mind to achieve an O(NlogN) solution.</p>
  
  <p>Hashing or other not-in-place solutions are not an option, because I am not able to duplicate my socks (though it could be nice if I could).</p>
  
  <p><strong>So, the question is basically:</strong></p>
  
  <p>Given a pile of <code>n</code> pairs of socks, containing <code>2n</code> elements (assume each sock has exactly one matching pair), what is the best way to pair them up efficiently with up to logarithmic extra space? (I believe I can remember that amount of info if needed.)</p>
  
  <p>I will appreciate an answer that addresses the following aspects:</p>
  
  <ul>
  <li>A general <em>theoretical</em> solution for a huge number of socks.</li>
  <li>The actual number of socks is not that large, I don't believe my spouse and I have more than 30 pairs. (And it is fairly easy to distinguish between my socks and hers; can this be used as well?)</li>
  <li>Is it equivalent to the <a href="http://en.wikipedia.org/wiki/Element_distinctness_problem" rel="noreferrer">element distinctness problem</a>?</li>
  </ul>