Here's my morning routine on a school day like today:

• Rise by alarm
• Sift through my sock drawer for 5 minutes trying to find a matching pair
• Select outer layers of clothes
• Do hygienic things
• Eat cereal while I check my sites
• Exit house, hopefully dressed, and proceed to bus stop

Clearly the sock search is the weakest link! I know what you're going to say, it's my fault for not sorting them right out of the laundry but even in that case the problem still persists. How can I efficiently sort my socks, especially at 7:30 in the morning?

So heck, might as well make use of my university education and see if there is any research done in the cutting-edge sock sorting algorithm field. Sure enough, the internet provides:

Rohit Parikh, Laxmi Parida, Vaughan R. Pratt: Sock Sorting: An Example of a Vague Algorithm. Logic Journal of the IGPL 9(5): (2001)

My normal method of sorting is a greedy algorithm. I pick up the first sock I see and go one by one through the rest of my socks trying to find a match. If things go according to plan (since my socks are pretty unique in coloration) I can sort through them pretty quickly, but in the worst case this search algorithm has O(n²) run time. That is, if there are n socks I'll have to make n comparisons with n other socks. This could explain my 5 minute sock search runtime. I just wish I had a faster CPU.

Parikh et. al. discuss a more interesting example in which socks can be matched vaguely based on their colors. For example, "suppose a dark gray sock will match either a dark gray sock or a charcoal gray sock and a black sock will match either a black or a charcoal gray sock", which unfortunately opens up possibilities for free-loading unmatched socks. The unmatched sock is never desirable but may be necessary depending on your sock shade spectrum.

Taking vagueness into account, my normal greedy algorithm will still run in O(n²) time in the worst case but linearly on average. More advanced algorithms are also discussed by Parikh. et. al. which eliminate the possibility of unmatched socks at the expense of some additional calculations but who has time for that?

It really makes a lot of sense. If my sock matching criteria is vague enough, on average, I'll find a match in linear time. The problem is that I just have such high standards. The solution to that is simple. I just have to consume alcohol in the morning in order to impair my judgment enough to get to class on time. Problem solved.