When I fold laundry, I pair up matching socks. Usually I put matching pairs of socks into the washing machine, then take a lot of individual socks out of the dryer; then, during folding, I recreate the pairs from a stream of individual socks by the following method. I maintain an "unpaired sock buffer", usually on my leg, which is initially empty. Then, for each sock in the sequence, I do a sequential search through this buffer for its mate. If I find the mate, I remove it from the buffer and form a pair; if I do not, I add the new sock to the buffer.
When the number of socks remains small, this works well; but it's slow for a large load of laundry; the average size of the buffer gets larger (I suspect it's proportional to the total number of socks) and so processing each sock takes longer. Other possible methods exist; for example, you could limit the sock buffer size and put overflow socks (either from the sequence or, to guard against stray single socks, from the sock buffer) into an overflow pile, which you'd process after the initial sock sequence; or you could sort the sequence into subsequences by some attribute such as color. The worst case for this problem is to compare every sock against every other sock. The worst case for the naive sock-buffer method isn't that bad; it happens when the sock sequence is palindromic. Here, you need only compare to half the other socks at most, and a quarter of them on average, which is four times better than the worst case. I wonder if other methods that take into account only equality of socks can do better. (Clearly, once you categorize socks by color, size, cut, and other attributes, you can use any of a variety of O(N lg N) sorting algorithms. Radix sorting with a radix around 5-10 seems to work best for me, beating out comparison-based schemes by a factor of five or so.)
