using System;
using System.Collections.Generic;
using System.Linq;
public class Test
{
private static int comparisons = 0;
public static void Main()
{
var r = new Random();
var input = new int[1000];
for (int i = 0; i < input.Length; i++) {
input[i] = r.Next();
}
var sorted = quicksort(input).ToArray();
Console.WriteLine(comparisons);
}
public static IEnumerable<T> quicksort<T>(IEnumerable<T> input) where T : IComparable<T>{
if (input.Count() <= 1) return input;
var pivot = input.FirstOrDefault();
var lesser = quicksort(input.Skip(1).Where(i => {
comparisons++;
return i.CompareTo(pivot) <= 0;
}));
var greater = quicksort(input.Where(i => {
comparisons++;
return i.CompareTo(pivot) > 0;
}));
return lesser.Concat(new T[] { pivot }).Concat(greater);
}
}
dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYzsKdXNpbmcgU3lzdGVtLkxpbnE7CgpwdWJsaWMgY2xhc3MgVGVzdAp7Cglwcml2YXRlIHN0YXRpYyBpbnQgY29tcGFyaXNvbnMgPSAwOwoJCglwdWJsaWMgc3RhdGljIHZvaWQgTWFpbigpCgl7CgkJdmFyIHIgPSBuZXcgUmFuZG9tKCk7CgkJdmFyIGlucHV0ID0gbmV3IGludFsxMDAwXTsKCQkKCQlmb3IgKGludCBpID0gMDsgaSA8IGlucHV0Lkxlbmd0aDsgaSsrKSB7CgkJCWlucHV0W2ldID0gci5OZXh0KCk7CgkJfQoJCQoJCXZhciBzb3J0ZWQgPSBxdWlja3NvcnQoaW5wdXQpLlRvQXJyYXkoKTsKCQkKCQlDb25zb2xlLldyaXRlTGluZShjb21wYXJpc29ucyk7Cgl9CgkKCXB1YmxpYyBzdGF0aWMgSUVudW1lcmFibGU8VD4gcXVpY2tzb3J0PFQ+KElFbnVtZXJhYmxlPFQ+IGlucHV0KSB3aGVyZSBUIDogSUNvbXBhcmFibGU8VD57CgkgICAgaWYgKGlucHV0LkNvdW50KCkgPD0gMSkgcmV0dXJuIGlucHV0OwoJICAgIHZhciBwaXZvdCA9IGlucHV0LkZpcnN0T3JEZWZhdWx0KCk7CgkgICAgdmFyIGxlc3NlciA9IHF1aWNrc29ydChpbnB1dC5Ta2lwKDEpLldoZXJlKGkgPT4gewoJICAgIAljb21wYXJpc29ucysrOwoJICAgIAlyZXR1cm4gaS5Db21wYXJlVG8ocGl2b3QpIDw9IDA7CiAgICAJfSkpOwoJICAgIHZhciBncmVhdGVyID0gcXVpY2tzb3J0KGlucHV0LldoZXJlKGkgPT4gewoJICAgIAljb21wYXJpc29ucysrOwoJICAgIAlyZXR1cm4gaS5Db21wYXJlVG8ocGl2b3QpID4gMDsKCSAgIAl9KSk7CgkgICAgcmV0dXJuIGxlc3Nlci5Db25jYXQobmV3IFRbXSB7IHBpdm90IH0pLkNvbmNhdChncmVhdGVyKTsKCX0KfQ==