Skip to content

Instantly share code, notes, and snippets.

@noblethrasher
Created December 24, 2013 16:42
Show Gist options
  • Save noblethrasher/8115437 to your computer and use it in GitHub Desktop.
Save noblethrasher/8115437 to your computer and use it in GitHub Desktop.
static IEnumerable<T> QuickSort<T>(IList<T> xs)
where T : IComparable<T>, IEquatable<T>
{
var stack = new Stack<Stack<T>>(new[] {new Stack<T>(xs)});
while (stack.Any())
{
var qs = stack.Pop();
var head = from q in qs where q.CompareTo(qs.Peek()) == 0 select q;
var less = from q in qs where q.CompareTo(qs.Peek()) < 0 select q;
var more = from q in qs where q.CompareTo(qs.Peek()) > 0 select q;
if (less.Any())
stack.Push(new Stack<T>(less));
if (more.Any())
{
stack.Push(new Stack<T>(head));
stack.Push(new Stack<T>(more));
}
else
foreach (var q in head)
yield return q;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment