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

最近関数型言語で「クイックソートが数行で書けるんだぜ！」みたいなアレがあるけどどう見てもクイックソートじゃないので
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
  

結論

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