Fun Question! This doesn't outperform OrderBy, but it does limit the repeated enumerations some.
public static IEnumerable<int> QSort2(IEnumerable<int> source)
{
if (!source.Any())
return source;
int first = source.First();
return source
.GroupBy(i => i.CompareTo(first))
.OrderBy(g => g.Key)
.SelectMany(g => g.Key == 0 ? g : QSort2(g));
}
I inadvertently generated a stackoverflow during development, as I QSorted when the Key == 0.
Just for fun I tested these solutions. I commited the cardinal performance testing sin (testing in debug mode), but I don't think that affects the big O effect we'll see. Here is the input (reversed input is worst case for quicksort)
IEnumerable<int> source = Enumerable.Range(0, 1000).Reverse().ToList();
- The triple concat-where solution took 71000 milliseconds.
- My solution took 330 milliseconds
- OrderBy.ToArray took 15 milliseconds (the timer's resolution, so actual time is probably less)
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…