Laundry - sort socks This is very artificial problem
Each sock has exactly 1 match. 
Can only take one random sock out of the Laundry basket.
Can only compare to the last random sock. 
If it matches you put the match aside. 
It is like you have a stack of socks and you can only match on the top sock. 
So if the match is down the sock pile you are not going to find a match. 
But you don't even get to look down the sock pile to even know if the match is in the sock pile. You only get to match to the top sock. 
You will eventually need to put the sock pile back in the Laundry basket. 
You can throw the unmatched socks back in the Landry basket at any time but they come out random  

On CS there is a guy telling me he has a better algorithm but he cheats and searches the sock pile for a match down the pile.  

public static void MatchSocks()
{
    Random rand = new Random();
    List&lt;int&gt; Laundry = new List&lt;int&gt;();
    List&lt;int&gt; Matched = new List&lt;int&gt;();
    List&lt;int&gt; Unmatched = new List&lt;int&gt;();
    int? LastUnmatched = null;
    int Sock;
    int count = 0;
    for (int i = 0; i &lt; 500; i++)
    {
        Laundry.Add(i);
        Laundry.Add(i);
    }
    while (true)
    {
        count++;
        if(Laundry.Count == 0)
        {
            if (Unmatched.Count == 0)
                break;
            Laundry = new List&lt;int&gt;(Unmatched);
            Unmatched.Clear();
            LastUnmatched = null;
        }
        Sock = Laundry.ElementAt(rand.Next(Laundry.Count));
        Laundry.Remove(Sock);
        if (LastUnmatched == null)
        {
            Unmatched.Add(Sock);
        }
        else
        {
            if (Sock == LastUnmatched)
            {
                Matched.Add(Sock);
                Unmatched.Remove(Sock);
            }
            else
            {
                Unmatched.Add(Sock);
            }
        }
        LastUnmatched = Sock;
    }
    Debug.WriteLine(count);
}
You're using some poor methods when there are better options available to the data types you've picked.

A huge bottleneck is hidden in those 2 lines:


Sock = Laundry.ElementAt(rand.Next(Laundry.Count));
Laundry.Remove(Sock);



Let's see why

General vs specific methods

ElementAt is an extension method of the type IEnumerable&lt;T&gt;, the List&lt;T&gt; is inheriting IEnumerable&lt;T&gt; but guess what, so are most of the collections in C#. That means when you write a method that is applicable to so many types, you need to make it as generic/general as possible while still maintaining reasonable performance, but of course using a concrete implementation of that method for said collection would be faster. You can do that because you are 100% sure that the optimizations will always be valid.

So the first thing is to replace the ElementAt() with normal indexer.

RemoveAt() vs Remove()

In most cases Remove() would be a O(n) operation where RemoveAt() would be O(1) operation. The first uses the latter internally so it's always better to use this method when you know what index you want to remove, guess what, you already know what index you're removing:

int index = rand.Next(Laundry.Count);
Sock = Laundry[index];
Laundry.RemoveAt(index);




Besides that you're never utilizing the collection Matched. You're just wasting time adding stuff into it without ever touching them.



Adding those changes made the code about 2.5 times faster. On average from 45ms  to about 17ms per run.