Question: How do you sort socks most efficiently from a pile?

Question:  How do you sort socks most efficiently from a pile?

Solution:  There are a bunch of assumptions here, so let's start listing them.  First, 
  - let's not assume that all pairs are distinct (e.g., you could have multiple pairs of the same socks).  
  - also, let's assume that there is no distinction between left foot/right foot for socks, (initially)   - that the number of socks pairs is a reasonable number of socks, (e.g., less than thirty),
  - the socks can quickly be compared for distinctness
  - you have sufficient table space for many piles

Let's start by thinking about how we do this in real life.  What I do when comparing socks, is I pick up one, and then go through the remaining socks to find the match.  In worst case, this requires:  (n-1) comparisons, then another (n-3) comparisons, then (n-5)...

Well, this is an O(n^2) algorithm.  So, this seems pretty slow.  But, when I do it, it certainly isn't this slow, as the algorithm has a few optimizations which aren't captured here.  

When I think of going through my socks, I somewhat remember my socks after the first pass through.  For example, I might remember that my blue sock was at the end, so I don't really have to look at all of the socks to figure out where this one goes.

Also, a comparison isn't really going through each sock one-by-one.  My vision/brain lets me look at many socks at once, say 10, and quickly find the match.  Some socks even stick out.  So, the problems is in reality, much faster than n^2, given these optimizations.

So, if I include these optimizations into the way that I sort socks, you could imagine that it's the same algorithm:
  - Prepare your sorting by moving the socks into subpiles of 10, with all socks visible
  - Pick up a sock, compare it until you find the match

With this optimization, the number of potential lookups is reduced by a factor of 10 (socks divided into 10s), and probably more given our memory of where socks are.  Given that we assume that we have fewer than 30 pairs of socks, finding a match is fewer than 6 look-ups, even not including memory.  If we include a 2x improvement with memory, this probably makes it under 3.  

This is almost constant time for each sock, and it goes down as we pair socks.  This is pretty darn good.

Now, let's imagine any other optimizations that might exist.  First, we could look to speed up the set-up process, by potentially spreading our socks out quickly and not being too rigorous on the number of socks in each pile.  

Or, we could consider moving socks into subpiles if they can easily be divided into distinct groups (e.g., blue vs. white) to reduce the lookup set.  

Perhaps we could get out of the problem all together, by doing something like using sock-clips when we wash our socks.

Also, some people have suggested 'sorting' the socks in order to solve this problem, but this is a challenging problem as socks have no clear, easily observable order (unlike numbers).  So, it's very hard to know if a red sock goes before blue, or after red.  And, even normal ways of comparing (e.g., some sort of color or length) gets difficult given real-world conditions like lots of white or dark blue socks of similar size, which makes the comparison operator complex and time-consuming.

In it's more generic form, the problem is something like, given n objects where each object in the set has a distinct pair, how can you most quickly sort the objects into pairs.  

We'll do this generic form next time.

<Please send bugs or optimizations!>

Thank you to Greg D. for suggesting this problem.