Sorting n elements into pairs (generic version of sorting socks)

Question:  Generalize sorting socks.  Assume that you have n objects where every object has potentially one or more pairs.  Sort the objects into pairs.

Answer:  This is a question where the assumptions really matter.  In the sock question, 

  - we struggled with the notion of order, e.g., given two socks, which one is greater?  

  - Also, we optimized by knowing that the human mind can compare more than two objects at once -- or at least pick out a like-object from a larger set quickly.  

  - We also assumed some element of memory, or that humans would remember, "The blue, striped sock was on the end."

So, let's assume that we have integers that we're trying to pair.  This is probably a reasonable assumption as a machine could assign some unique number to each element in our set.  Then, let's also assume that our comparison is confined to two elements at a time, and there is no memory.

In this case, the most obvious answer would be to sort the set.  This would yield an nlogn solution and we could then easily go through and would have our pairs set.

However, this actually does more than we need.  We would end up with a sorted set, which is not required.  Only paired elements must be together.

Ok, let's do better.

Imagine what we want to do.  We want to go through our set and put each element in a unique spot, then at the end, each 'spot' would consist of like pairs.

And, getting into spots must be a fast, or constant time operations, or else we're no faster than the sorting solution.

If you do an example, this quickly looks like putting each element into a hash table with n/2 hash buckets.  

Then, the total algorithm is clear:

  - Create a hash table with n/2 hash buckets.

  - Go through the list and hash into the hash table.

  - At the end, look at every hash bucket and sort if there are more than 2 elements.

  

Each hash table should be mostly unique and can quickly be ordered if not unique.

Well, this works.  

This is a good example of how machines often do things differently than the human brain, and potentially an example of where a machine might not be good, especially if comparison took a long time -- e.g., comparing two socks is a relatively complex operation if given two photos given orientation, folds, minor wear differences, yet it is something that humans can do intuitively.  But, that's another discussion!

/* Please send me any bugs or optimizations */