using System;

using System.Linq;

using System.Diagnostics;

using System.Collections.Generic;

public class Program

{

    public static int Main()

    {

        var random = new Random();

        var arraySize = 6000;

        var testData = Enumerable.Range(0, arraySize).Select(x => random.Next(0, arraySize)).ToArray();

        var stopwatch = new Stopwatch();

        stopwatch.Start();

        QuickSort(testData);

        stopwatch.Stop();

        Console.WriteLine($"Custom quicksort: {stopwatch.ElapsedTicks} ticks, {stopwatch.ElapsedMilliseconds} milliseconds");

        stopwatch.Restart();

        Array.Sort(testData);

        stopwatch.Stop();

        Console.WriteLine($"Array.Sort: {stopwatch.ElapsedTicks} ticks, {stopwatch.ElapsedMilliseconds} milliseconds");

        return 1;

    }

    // Пример реализации сортировки Хоара

    // Pivot выбирается рандомно

    static IEnumerable<T> QuickSort<T>(IEnumerable<T> i) where T : IComparable

    {

        if (!i.Any()) return i;

        var p = i.ElementAt(new Random().Next(0, i.Count() - 1));

        return QuickSort(i.Where(x => x.CompareTo(p) < 0)).Concat(i.Where(x => x.CompareTo(p) == 0)).Concat(QuickSort(i.Where(x => x.CompareTo(p) > 0)));

    }

}