クイックソートと偽クイックソートの比較

最近関数型言語で「クイックソートが数行で書けるんだぜ！」みたいなアレがあるけどどう見てもクイックソートじゃないので
C#でそのソートとクイックソートを比較してみた。

計測に使ったプヨグヤム
```csharp:qsort.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Reflection;

namespace Test
{
    class Program
    {
        public static int[] arr;

        static void Main(string[] args)
        {
            arr = GenerateArray(new Random());

            Console.Write("QuickF"); Calculate(QuicksortF);
            Console.Write("QuickT"); Calculate(QuicksortT);

            Console.ReadKey();
        }

        static void Calculate(Action<int[], int, int> method)
        {
            Stopwatch sw = new Stopwatch();

            var array = new int[arr.Length];
            Array.Copy(arr, array, arr.Length);

            sw.Reset();
            sw.Start();
            method(array, 0, array.Length - 1);
            sw.Stop();

            Console.WriteLine(":{1}ms", method, sw.ElapsedMilliseconds);
        }

        static int[] GenerateArray(Random rand)
        {
            return Enumerable.Range(0, 1000000).Select(x => rand.Next(100000)).ToArray();
        }

        static void QuicksortF(int[] array, int left, int right)
        {
            var pt = GetPt(array, 0, array.Length-1);

            var lList = new List<int>();
            var rList = new List<int>();
            var cList = new List<int>();

            var list = array.ToList();

            foreach(var v in array)
            {
                if (v < pt) lList.Add(v); else if (v > pt) rList.Add(v); else cList.Add(v);
            }

            var arrayL = lList.ToArray();
            var arrayR = rList.ToArray();
            var arrayC = cList.ToArray();

            if (arrayL.Length > 0) QuicksortF(arrayL, 0, lList.Count - 1);
            if (arrayR.Length > 0) QuicksortF(arrayR, lList.Count, lList.Count + rList.Count - 1);

            var totalList = arrayL.ToList();
            totalList.AddRange(arrayC);
            totalList.AddRange(arrayR);

            for (var i = 0; i < totalList.Count; i++)
            {
                ReplaceF(ref array[i], totalList[i]);
            }
        }

        static void ReplaceF(ref int var, int val)
        {
            var = val;
        }

        static void QuicksortT(int[] array, int left, int right)
        {
            var pt = GetPt(array, left, right);

            int i = left, j = right;

            while (true)
            {
                while (array[i] < pt) i++;

                while (pt < array[j]) j--;

                if (i >= j) break;

                SwapT(ref array[i], ref array[j]);
                i++; j--;
            }

            if (left < i - 1)  QuicksortT(array, left, i - 1);
            if (j + 1 < right) QuicksortT(array, j + 1, right);
        }

        static void SwapT(ref int a, ref int b)
        {
            var tmp = a;
            a = b;
            b = tmp;
        }

        static int GetPt(int[] array, int left, int right)
        {
            int l = array[left];
            int r = array[right];
            int c = array[(left + right) / 2];
            int[] a = new int[] { l, r, c };
            Array.Sort(a);
            return a[1];
        }
    }
}
```
QuicksortFがその偽ソートでQuicksortTが実際のクイックソート。
平均はとらなかったけど察して

#### 要素数100万, 乱数0～99999
* QuicksortF: 873ms
* QuicksortT: 331ms  

#### 要素数1000万, 乱数0～99999
* QuicksortF: 7821ms
* QuicksortT: 3603ms  

#### 要素数100万, 乱数0～99
* QuicksortF: 283ms
* QuicksortT: 346ms  

#### 要素数100万, 乱数0～9
* QuicksortF: 124ms
* QuicksortT: 307ms  

# 結論
偽クイックソートはどう見てもマージソート