中央値を求めるぞ

MedianImpls.cs

using System;

namespace MedianBenchmark
{
    public static class MedianImpls
    {
        public static int ArraySort(int[] data)
        {
            var w = (int[])data.Clone();
            Array.Sort(w);
            return w.Length % 2 == 0
                ? (w[w.Length / 2] + w[w.Length / 2 - 1]) / 2
                : w[w.Length / 2];
        }

        public static int InsertSort(int[] data)
        {
            var capacity = data.Length / 2 + 1;
            var w = new int[capacity];
            w[0] = data[0];
            var wCount = 1;

            for (var i = 1; i < data.Length; i++)
            {
                var v = data[i];
                var j = wCount - 1;
                if (w[j] <= v)
                {
                    if (wCount < capacity)
                        w[wCount++] = v;
                    continue;
                }

                if (wCount < capacity)
                {
                    wCount++;
                    j++;
                }

                for (; j > 0 && w[j - 1] > v; j--)
                    w[j] = w[j - 1];

                w[j] = v;
            }

            return data.Length % 2 == 0
                ? (w[capacity - 1] + w[capacity - 2]) / 2
                : w[capacity - 1];
        }

        public static int HeapSort(int[] data)
        {
            var capacity = data.Length / 2 + 1;
            var heap = new RestrictedBinaryHeap<int>(capacity);

            var i = 0;
            for (; i < capacity; i++)
                heap.Push(data[i]);

            for (; i < data.Length; i++)
            {
                if (data[i] < heap.GetHead())
                    heap.ReplaceHead(data[i]);
            }

            return data.Length % 2 == 0
                ? (heap.GetHead() + heap.GetSecond()) / 2
                : heap.GetHead();
        }

        private struct RestrictedBinaryHeap<T> where T : IComparable<T>
        {
            private readonly T[] _array;
            private int _count;

            public RestrictedBinaryHeap(int capacity)
            {
                _array = new T[capacity];
                _count = 0;
            }

            public void Push(T value)
            {
                var nodeIndex = _count++;

                while (nodeIndex > 0)
                {
                    var parentIndex = (nodeIndex - 1) / 2;

                    if (value.CompareTo(_array[parentIndex]) <= 0) break;

                    _array[nodeIndex] = _array[parentIndex];
                    nodeIndex = parentIndex;
                }

                _array[nodeIndex] = value;
            }

            public void ReplaceHead(T value)
            {
                var nodeIndex = 0;

                while (true)
                {
                    var childIndex = 2 * nodeIndex + 1;

                    if (childIndex >= _count) break;

                    if (childIndex + 1 < _count && _array[childIndex + 1].CompareTo(_array[childIndex]) > 0)
                        childIndex++;

                    if (value.CompareTo(_array[childIndex]) >= 0) break;

                    _array[nodeIndex] = _array[childIndex];
                    nodeIndex = childIndex;
                }

                _array[nodeIndex] = value;
            }

            public T GetHead() => _array[0];

            public T GetSecond() => _count < 3 || _array[1].CompareTo(_array[2]) >= 0 ? _array[1] : _array[2];
        }
    }
}

Program.cs

using System;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

namespace MedianBenchmark
{
    class Program
    {
        static void Main(string[] args)
        {
            //var case1 = new[] { 1, 2, 5, 7, 3, 6, 4, 2 };
            //Console.WriteLine(MedianImpls.ArraySort(case1));
            //Console.WriteLine(MedianImpls.InsertSort(case1));
            //Console.WriteLine(MedianImpls.HeapSort(case1));

            //var case2 = new[] { 5, 8, 4, 6, 8 };
            //Console.WriteLine(MedianImpls.ArraySort(case2));
            //Console.WriteLine(MedianImpls.InsertSort(case2));
            //Console.WriteLine(MedianImpls.HeapSort(case2));

            BenchmarkRunner.Run<StreamMedianBenchmark>();
        }
    }

    public class StreamMedianBenchmark
    {
        [Params(781658341, 817659145, 91554150, 1963572926)]
        public int Seed;

        [Params(50, 500, 5000)]
        public int Count;

        private int[] _data;

        [GlobalSetup]
        public void GlobalSetup()
        {
            var random = new Random(Seed);
            _data = new int[Count];
            for (var i = 0; i < _data.Length; i++)
                _data[i] = random.Next();
        }

        [Benchmark]
        public int ArraySort()
        {
            return MedianImpls.ArraySort(_data);
        }

        //[Benchmark]
        //public int InsertSort()
        //{
        //    return MedianImpls.InsertSort(_data);
        //}

        [Benchmark]
        public int HeapSort()
        {
            return MedianImpls.HeapSort(_data);
        }
    }
}

StreamMedianBenchmark-report-github.md

BenchmarkDotNet=v0.10.8, OS=Windows 10.0.16215
Processor=Intel Core i7-3770 CPU 3.40GHz (Ivy Bridge), ProcessorCount=8
Frequency=3312786 Hz, Resolution=301.8607 ns, Timer=TSC
dotnet cli version=1.0.4
  [Host]     : .NET Core 4.6.25211.01, 64bit RyuJIT
  DefaultJob : .NET Core 4.6.25211.01, 64bit RyuJIT

Method	Seed	Count	Mean	Error	StdDev
ArraySort	91554150	50	497.5 ns	3.864 ns	3.615 ns
HeapSort	91554150	50	368.2 ns	2.266 ns	2.008 ns
ArraySort	91554150	500	4,996.8 ns	50.233 ns	46.988 ns
HeapSort	91554150	500	5,449.7 ns	48.837 ns	43.293 ns
ArraySort	91554150	5000	203,393.7 ns	1,308.735 ns	1,224.192 ns
HeapSort	91554150	5000	169,941.7 ns	877.339 ns	820.663 ns
ArraySort	781658341	50	519.2 ns	3.750 ns	3.131 ns
HeapSort	781658341	50	368.2 ns	4.268 ns	3.992 ns
ArraySort	781658341	500	5,653.1 ns	47.378 ns	44.317 ns
HeapSort	781658341	500	5,553.6 ns	39.706 ns	35.198 ns
ArraySort	781658341	5000	211,548.5 ns	2,447.282 ns	2,289.189 ns
HeapSort	781658341	5000	166,809.1 ns	488.767 ns	408.143 ns
ArraySort	817659145	50	503.1 ns	7.500 ns	6.649 ns
HeapSort	817659145	50	351.6 ns	3.020 ns	2.825 ns
ArraySort	817659145	500	5,436.5 ns	62.462 ns	58.427 ns
HeapSort	817659145	500	5,283.7 ns	21.776 ns	18.184 ns
ArraySort	817659145	5000	209,180.6 ns	1,233.291 ns	1,093.280 ns
HeapSort	817659145	5000	171,166.3 ns	1,894.112 ns	1,679.081 ns
ArraySort	1963572926	50	488.6 ns	5.213 ns	4.353 ns
HeapSort	1963572926	50	393.0 ns	4.678 ns	4.147 ns
ArraySort	1963572926	500	5,463.1 ns	84.668 ns	79.199 ns
HeapSort	1963572926	500	5,504.1 ns	50.072 ns	41.812 ns
ArraySort	1963572926	5000	214,190.8 ns	3,245.934 ns	2,710.501 ns
HeapSort	1963572926	5000	170,127.4 ns	2,313.153 ns	2,163.724 ns