C# QuickSort using Continuation Passing Style (As requested by a comment)

using System;

using System.Linq;

using System.Collections.Generic;

public static class ListExtensions

{

    public static Tuple<IEnumerable<T>, IEnumerable<T>> Partition<T>(

         this IEnumerable<T> items, Func<T, bool> p)

    {

        var xs = items.Where(p);

        var ys = items.Except(xs);

        return Tuple.Create(xs, ys);

    }

    public static IEnumerable<T> Loop<T>(

        IEnumerable<T> xs,

        Func<IEnumerable<T>, IEnumerable<T>> cont) where T : IComparable

    {

        if (!xs.GetEnumerator().MoveNext())

            return cont(new T[0]);

        else

        {

            var x = xs.First();

            var xsp = xs.Skip(1);

            var parts = xsp.Partition(y => y.CompareTo(x) > 0);

            return Loop<T>(parts.Item1, lacc =>

                   Loop<T>(parts.Item2, racc =>

                       cont(lacc.Concat(new[] { x }).Concat(racc))));

        }

    }

    public static IEnumerable<T> QuickSort<T>(this IEnumerable<T> xs)

                                 where T : IComparable

    {

        return Loop<T>(xs, x => x);

    }

}