MergeSort.cs

public static class ArrayExtensions
{
    public static void MergeSort(this int[] array, int left, int right)
    {
        if (left >= right)
            return;
        var mid = (left + right) / 2;
        MergeSort(array, left, mid);
        MergeSort(array, mid + 1, right);
        DoMerge(array, left, mid, right);
    }

    private static void DoMerge(int[] array, int start, int mid, int end)
    {
        var temp = new Queue<int>();
        var leftIndex = start;
        var rightIndex = mid + 1;

        while (leftIndex <= mid && rightIndex <= end)
        {
            if (array[leftIndex] <= array[rightIndex])
            {
                temp.Enqueue(array[leftIndex]);
                leftIndex++;
            }
            else
            {
                temp.Enqueue(array[rightIndex]);
                rightIndex++;
            }
        }

        while (leftIndex <= mid)
        {
            temp.Enqueue(array[leftIndex]);
            leftIndex++;
        }

        while (rightIndex <= end)
        {
            temp.Enqueue(array[rightIndex]);
            rightIndex++;
        }

        for (var i = start; i <= end; i++)
        {
            array[i] = temp.Dequeue();
        }
    }
    
    public static int BinarySearch(this int[] array, int key)
    {
        int min = 0;
        int max = array.Length - 1;

        while (min <= max)
        {
            int mid = (min + max) / 2;
            if (key == array[mid])
                return mid;
            else if (key < array[mid])
                max = mid - 1;
            else
                min = mid + 1;
        }
        return -1;
    }
}

    // https://gist.github.com/lbsong/6833729
    class Program
    {
        static void Main(string[] args)
        {
            int[] a = { 5, 3, 6, 4, 2, 9, 1, 8, 7 };
            QuickSort(a);
        }

        static void QuickSort(int[] a)
        {
            QuickSort(a, 0, a.Length - 1);
        }

        static void QuickSort(int[] a, int start, int end)
        {
            if (start >= end)
            {
                return;
            }

            int num = a[start];

            int i = start, j = end;

            while (i < j)
            {
                while (i < j && a[j] >= num)
                {
                    j--;
                }

                a[i] = a[j];

                while (i < j && a[i] < num)
                {
                    i++;
                }

                a[j] = a[i];
            }

            a[i] = num;
            QuickSort(a, start, i - 1);
            QuickSort(a, i + 1, end);
        }
    }