Reason Solution #2: Naive Partial Sort is Slower

[mpetito]

I've run this test several times, and each time the Naive Partial Sort take a few seconds longer than the basic Naive Sort. It's very possible this is simply due to small sample size errors, but if any of my dear readers sees a reason why the Naive Partial Sort would consistently perform worse than the Naive Sort, I'd be happy to hear it.

The reason Solution #2 is slower is precisely because it finds a partial match sooner. This means the average index of a match is closer to the front of the sock array (index 0), whereas the average match in Solution #1 is nearer to the middle of the array.

Since the algorithm calls Remove on List<Sock>, the average index of each match affects the time to remove the match. Remove calls into RemoveAt which copies all of the elements after the removed index using Array.Copy.

As the match is always nearer to the front of the array, this means more copying since the balance of the array (the portion after the match) is on average longer than in Solution #1.

If you had used a HashSet<Sock> or other collection with constant removal time, then my guess is you would have seen faster execution with Solution #2 (although still return an unsorted result).

[exceptionnotfound]

I moved this comment to my blog. If you'd like to take credit for it, post it there and I'll remove my copy. Thanks for the explanation!