I hope I can contribute something new to this problem. I noticed that all of the answers neglect the fact that there are two points where you can perform **preprocessing**, without slowing down your overall laundry performance.

Also, we don't need to assume a large number of socks, even for large families. Socks are taken out of the drawer and are worn, and they are tossed in a place (maybe a bin) where they stay before being laundered. While I wouldn't call said bin a LIFO-Stack, I'd say it is safe to assume that

- people toss both of their socks roughly in the same area of the
bin,
- the bin is not randomized at any point, and therefore
- any subset took from the top of this bin generally contains both
socks of a pair.

Since all washing machines I know about are limited in size (regardless of how many socks you have to wash), and the actual randomizing occurs in the washing machine, no matter how many socks we have, we always have small subsets which contain almost no singletons.

Our two preprocessing stages are "putting the socks on the clothesline" and "Taking the socks from the clothesline", which we have to do, in order to get socks which are not only clean but also dry. As with washing machines, clotheslines are finite, and I assume that we have the whole part of the line where we put our socks in sight.

Here's the algorithm for put_socks_on_line():

```
while (socks left in basket) {
take_sock();
if (cluster of similar socks is present) {
Add sock to cluster (if possible, next to the matching pair)
} else {
Hang it somewhere on the line, this is now a new cluster of similar-looking socks.
Leave enough space around this sock to add other socks later on
}
}
```

Don't waste your time moving socks around or looking for the best match, this all should be done in O(n), which we would also need for just putting them on the line unsorted.
The socks aren't paired yet, we only have several similarity clusters on the line. It's helpful that we have a limited set of socks here, as this helps us to create "good" clusters (for example, if there are only black socks in the set of socks, clustering by colours would not be the way to go)

Here's the algorithm for take_socks_from_line():

```
while(socks left on line) {
take_next_sock();
if (matching pair visible on line or in basket) {
Take it as well, pair 'em and put 'em away
} else {
put the sock in the basket
}
```

I should point out that in order to improve the speed of the remaining steps, it is wise not to randomly pick the next sock, but to sequentially take sock after sock from each cluster.
Both preprocessing steps don't take more time than just putting the socks on the line or in the basket, which we have to do no matter what, so this should greatly enhance the laundry performance.

After this, it's easy to do the hash partitioning algorithm. Usually, about 75% of the socks are already paired, leaving me with a very small subset of socks, and this subset is already (somewhat) clustered (I don't introduce much entropy into my basket after the preprocessing steps). Another thing is that the remaining clusters tend to be small enough to be handled at once, so it is possible to take a whole cluster out of the basket.

Here's the algorithm for sort_remaining_clusters():

```
while(clusters present in basket) {
Take out the cluster and spread it
Process it immediately
Leave remaining socks where they are
}
```

After that, there are only a few socks left. This is where I introduce previously unpaired socks into the system and process the remaining socks without any special algorithm - the remaining socks are very few and can be processed visually very fast.

For all remaining socks, I assume that their counterparts are still unwashed and put them away for the next iteration. If you register a growth of unpaired socks over time (a "sock leak"), you should check your bin - it might get randomized (do you have cats which sleep in there?)

I know that these algorithms take a lot of assumptions: a bin which acts as some sort of LIFO stack, a limited, normal washing machine, and a limited, normal clothesline - but this still works with very large numbers of socks.

About parallelism:
As long as you toss both socks into the same bin, you can easily parallelize all of those steps.

405I use pigeon hole principle to pair exactly one from the laundry pile. I have 3 different colors of socks (Red,Blue and Green) and 2 pairs of each color. I pick up 4 number of socks each time and I always make up a pair and get to work. – Srinivas – 2013-01-19T15:37:34.983

2I would think you could simplify it somewhat by assuming that some subset of pairs of socks are fungible; I have about six pairs of socks that are identical. Also: neat question! – Dave – 2013-01-19T15:37:45.150

1Pick your favourite ordering principle (colour, texture, thickness), sort by that, pick adjacent pairs – sehe – 2013-01-19T15:42:31.183

52Yet another pigeon hole principle: if you take a subset of n/2 +1 socks, there

must beat least one pair in this subset. – wildplasser – 2013-01-19T15:57:54.0876also, you discard hashes beccause you cant make copies, but note that its easily possible to make a hash set that doesnt need copies, both in computing and in laundry. – Mooing Duck – 2013-01-19T17:42:42.563

2@MooingDuck: If you have something specific in mind, please post it, note that I do not "discard it" - this is only my initial thaughts - that might be wrong, the question itself does not forbid hashing, it only requires the algorithm to be in-place (and efficient). As said, I will also appreciate an answer that deals with the other aspects (small/large scale, and equivalence to the distinctness problem - that will show O(nlogn) is basically the best I can get without extra space) – amit – 2013-01-19T17:54:19.250

6

remark that if you had an infinite number of different symmetric pairs of socks (i.e. left=right), then, in fact, just picking out one of each is not possible unless you accept the axiom of choice (http://en.wikipedia.org/wiki/Axiom_of_choice). What consequence does this have on pairing? how is this relevant to computability? http://math.stackexchange.com/questions/269902/what-is-the-relationship-between-zfc-and-turing-machine

– thang – 2013-01-20T04:52:15.1531

By the way, this is better known (sort of) as the game of Concentration) - making pairs from a large random group.

– Izkata – 2013-01-20T06:13:47.8602A good algorithm to do by hand might be a shift-reduce algorithm. Add a new sock to the pile randomly and as soon as you have a pair on top, "reduce" and take the pair away. Eventually you'll get most of them. Remainder can be manually handled or algorithm restarted. Not computer science in the slightest but reasonably good since you can cheat a bit and pick up the right sock sometimes. – doug65536 – 2013-01-20T06:56:45.130

34

Great question! You might be interested in my article on a related problem, which is a discussion of the probability of pulling two matched socks out of the pile: http://blogs.msdn.com/b/ericlippert/archive/2010/03/22/socks-birthdays-and-hash-collisions.aspx

– Eric Lippert – 2013-01-20T19:08:45.353Pigeonhole principle : http://en.wikipedia.org/wiki/Pigeonhole_principle

– Nabil Kadimi – 2013-01-21T20:34:28.1209Add an extra pointer to the sock class that will point to the sock's pair. – AJMansfield – 2013-07-11T20:49:21.137

266Why not spawn a child and

`waitpid`

so that, as the parent, you're not even sorting any socks yourself? – Mxyk – 2013-09-06T16:48:54.320101I solved this problem by only owning white knee-high socks. They all match. I could simply grab any two socks at random from the pile and they would match. I further simplify the problem by NOT pairing the socks. I have a sock drawer that I simply throw all my socks into, unpaired. I grab two at random from the drawer every morning. I've simplified it down to O(0). Can't get any simpler than that. :) – Lee – 2013-09-06T20:18:28.037

14This is O(1) anyway - there's a constant limit to the number of socks that will fit in any particular washing machine or sock drawer. – Steve314 – 2013-09-07T01:51:31.923

1@Steve314 So parallelize and use multiple sock drawers. – Thomas – 2013-09-14T04:07:38.053

5If you'd be able to duplicate socks, "hashing" wouldn't be the most efficient answer ;) – sfussenegger – 2013-09-19T13:46:27.587

1

This paper discusses a related problem : http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.178.4654&rep=rep1&type=pdf

– Erel Segal-Halevi – 2013-10-16T12:20:55.0431

Here is another related link: http://www.mail-archive.com/[email protected]/msg00084.html

– Erel Segal-Halevi – 2013-10-16T12:26:50.10310I know this doesn't answer your question in a theoretical sense, but practically speaking, nobody's looking at your socks. Not pairing them is O(k). – sqykly – 2013-11-10T11:25:32.130

7Laundry day is boring as it is. To eliminate the drag of sock sorting you should be doing it lazily: pour all (unmatched) socks in drawer, each morning pick two that look (kind of) the same. – Marcus – 2013-12-06T11:36:48.900

1I think in this case avoidance is the best solution: I have only one type of socks and therefore it's O(n) and requires a minimum of memory... :-) – Francois Bourgeois – 2013-12-24T14:24:29.693

14This question is chock full of engineering tunnel vision. Not everything's a nail. Sorting real life socks is very dependent on the performance limitations of the human visual cognitive system and her manipulators. We can, to an extent, pattern-match socks using our parallel vision processing (visual cortex FTW). We can also, to an extent, do motion planning in parallel with acquiring the next pair of socks to pick out of the pile. The theoretic description of the algorithmic complexity of real life sock searching is nothing like what you describe. – Kuba Ober – 2014-03-25T21:05:03.443

8IOW: Real-life sock sorts are completely insensitive to what underlying algorithm you use, and you can't really choose an algorithm because your visual and motor cortex has already chosen one for you. An optimal one, as far as I can tell. The manipulation time trumps everything else. My finding is (and damn I've spent a couple of hours recording myself and analyzing the recordings): you can easily saturate your manipulators, and that's the end of it. All you need is a sufficiently big table. The CS stuff comes in only if your load doesn't fit on one table. – Kuba Ober – 2014-03-25T21:05:56.270

@thang, you don't need to assume the Axiom of Choice if the number of socks is countable. – Apprentice Queue – 2014-04-02T23:21:06.587

@ApprenticeQueue say you're right, what would the choice function look like? I think that you are (provably) wrong, but to give a hint, have a look at this: http://en.wikipedia.org/wiki/Axiom_of_countable_choice (a weaker version of AC). To prove that even axiom of countable choice is independent of ZF is difficult and uses forcing.

– thang – 2014-04-03T08:38:15.7631You can save memory by immediately stuffing the pile from the basket to the drawer instead of spreading them out on a surface (to find matching pairs). Just look for a matching pair from the drawer when you need it. – user1164937 – 2014-04-30T03:13:19.507

9I am sure someone has already posted this, but you are inferring from the incorrect assumption that there is a pair for each sock. I mean - come on, do you really think that each sock that you are laundering has a matching one... – Vasil Dininski – 2014-04-30T22:33:42.937

3The optimum solution to the sock pairing problem is to put them into the laundry

as a pair. This reduces sort time tozeroand resolves the single sock problem. – Keith – 2014-05-02T06:12:27.043@amit you wrote using your naive technique you were doing

This requires iterating over n/2n/4 = n2/8 socks on average.*. What is the reasoning for this? How are the terms n/2 and n/4 appearing? – Geek – 2014-05-07T15:02:45.187@Geek You need to pair n/2 socks (this is where n/2 came from). by taking one sock, and finding its match. On average, you need to go through half of the left socks. At the first iteration this number is n/2, at second, (n/2)/2, ... the average of n/2,(n-2)/2,(n-4)/2,...,2/2 is n/4. – amit – 2014-05-07T15:38:12.210

3The other problem that everyone else seemed to overlook is the problem of finding a sock's exact match (not just same color and size). I always keep socks with their respective partners so that they wear the same, so if I don't find the exact sock I have always worn with the other sock, they will feel different (unacceptable to my OCD programmer mind) even though they originated from the

exact same package. – cnsumner – 2014-07-07T20:25:15.9405I have also solved the practical problem in O(1) time, by only buying black socks in packs of 50 pairs. It's interesting how many Stack Overflow posters have found the same solution! – Persixty – 2014-11-19T19:29:18.260

3How do you account for the sock without its pair that the dryer monster ate? – woot – 2015-02-24T05:07:57.817

My solution is to only have 1 type of socks of 1 color. This way I can pick any two and they always match. – user985366 – 2017-03-05T14:17:01.283

For socks, I think using a bucket sort would be the most efficient method. have your pile in one spot and your buckets in another. pull a sock, put it in a new pile of socks that match that sock. as long as you have enough table space, you can sort your socks in O(n) time, which is the lower limit, if you're doing this yourself. adding extra workers allows you to push towards O(log n) – Chris Phillips – 2017-09-29T13:23:33.700

your assumption about matching pairs is soooo removed from reality. even with two

`parallel.task(child).waitpid.all`

the performance gain the accepted answer promises is outweighed by the exponential decline of the number of matching specimen in the pile over time. – dlatikay – 2018-01-22T22:03:07.5701I do not have any matching pairs of socks. When you put a set of matching pairs of socks into the washing machine, what comes out is a random number of socks (usually odd), none of which match each other. This is a well-known property of washing machines. – Michael Kay – 2018-03-05T15:26:45.410