using System;

​

public class Program

{

    public static void Main()

    {

        var quickSorter = new MergeSorter();

​

        var testData = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 };

        var expected = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 };

        quickSorter.Sort<int>(testData);

        Console.WriteLine(string.Format("Expected: {0}, actual: {1}", string.Join(", ", expected), string.Join(", ", testData)));

        testData = new int[] { 1, 3, 2, 5, 4, 6, 8, 7 };

        expected = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 };

        quickSorter.Sort<int>(testData);

        Console.WriteLine(string.Format("Expected: {0}, actual: {1}", string.Join(", ", expected), string.Join(", ", testData)));

        testData = new int[] { 8, 7, 6, 5, 4, 3, 2, 1 };

        expected = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 };

        quickSorter.Sort<int>(testData);

        Console.WriteLine(string.Format("Expected: {0}, actual: {1}", string.Join(", ", expected), string.Join(", ", testData)));

    }

}

​

public class MergeSorter

{

    public void Sort<T>(T[] data) where T: IComparable

    {

        Sort(data, 0, data.Length - 1);

    }

    private void Sort<T>(T[] data, int left, int right) where T: IComparable

    {

        if(left < right) {

            int middle = left + (right - left) / 2;

            Sort(data, left, middle); 

            Sort(data, middle + 1, right); 

            Merge(data, left, middle, right);

        }

    }

    private void Merge<T>(T[] data, int left, int middle, int right) where T: IComparable

    {

        var leftLength = middle -left + 1;

        var rightLength = right - middle;

        var leftPart = new T[leftLength];

        var rightPart = new T[rightLength];

        Array.Copy(data, left, leftPart, 0, leftLength);

        Array.Copy(data, middle + 1, rightPart, 0, rightLength);

        var leftPointer = 0;

        var rightPointer = 0;

        var mergePointer = left;

        while(leftPointer < leftLength && rightPointer < rightLength) {

            if(leftPart[leftPointer].CompareTo(rightPart[rightPointer]) < 0) {

                data[mergePointer] = leftPart[leftPointer];

                leftPointer++;

            }

            else {

                data[mergePointer] = rightPart[rightPointer];

                rightPointer++;

            }

            mergePointer++;

        }

        while(leftPointer < leftLength) {

            data[mergePointer] = leftPart[leftPointer];

            leftPointer++;

            mergePointer++;

        }

        while(rightPointer < rightLength) {

            data[mergePointer] = rightPart[rightPointer];

            rightPointer++;

            mergePointer++;

        }

    }

}