Быстрая сортировка на C# в одну строчку

Недавно я увидел быструю сортировку на Haskell ^[1]. Всего 2 строчки. И решил попробовать написать аналогичную сортировку на C#. Получилось еще лучше — всего одна строчка, хоть и длинная и совсем не такая изящная. Подробности под катом.

Вот сама сортировка:

private static Func<int[], int[]> QSortArray =
            arr => arr.Length.Equals(0)
                ? new int[] {}
                : (QSortArray(Array.FindAll(arr, num => num.CompareTo(arr[0]) < 0))
                    .Concat(Array.FindAll(arr, num => num.CompareTo(arr[0]) == 0))
                    .Concat(QSortArray(Array.FindAll(arr, num => num.CompareTo(arr[0]) > 0)))).ToArray();

Выглядит сложновато, да, но при знании используемых тут методов разобраться вполне можно. Как работает Func<> проще всего посмотреть в MSDN ^[2], а остальное я поясню:

Тернарный оператор сравнивает длину массива с нулем. Если длина массива нулевая, то возвращает пустой массив. Если длина ненулевая, начинается самое интересное: сначала находятся все элементы из массива, меньшие первого, с помощью Array.FindAll и сортируются. Аналогично со всеми элементами, равными первому (этих, сортировать, разумеется, не нужно), большими первого. Затем все это «склеивается» с помощью Concat, который возвращает тип IEnumerable, поэтому в конце мы приводим все к массиву методом ToArray(). Подробнее об используемых методах можно посмотреть опять же, в MSDN ^[3].

private static Func<List<int>, List<int>> QSortList =
            arr => arr.Count.Equals(0)
                ? new List<int>()
                : (QSortList(arr.FindAll(num => num.CompareTo(arr[0]) < 0))
                    .Concat(arr.FindAll(num => num.CompareTo(arr[0]) == 0))
                    .Concat(QSortList(arr.FindAll(num => num.CompareTo(arr[0]) > 0)))).ToList();

private static Func<IEnumerable<int>, IEnumerable<int>> QSortEnumerable =
            arr => arr.Count().Equals(0)
                ? new List<int>()
                : (QSortEnumerable(arr.Where(num => num.CompareTo(arr.First()) < 0)).
                    Concat(arr.Where(num => num.CompareTo(arr.First()) == 0)).
                    Concat(QSortEnumerable(arr.Where(num => num.CompareTo(arr.First()) > 0))));

Сортировка, разумеется, значительно медленнее библиотечной — раз в 20 (тестировал на массиве из 5 миллионов чисел: моя сортировка 10 секунд, библиотечная — 0.5 секунды), так что практическую ценность вряд ли имеет. Другого ожидать от алгоритма в одну строку и не стоило, хотя она все равно намного быстрее практически любой квадратичной.