编辑代码

using System;

public class HelloWorld
{
    public static void Main()
    {
        int[] arr = new int[] { 8, 1, 6, 7, 2, 6, 9, 4 };
        MergeSort(arr, 0, arr.Length-1);
        foreach (int i in arr)
        {
            Console.Write(i + " ");
        }
    }

    public static void MergeSort(int[] array, int left, int right)
        {
            if (left >= right) return;
            int middle = (left + right) / 2;
            MergeSort(array, left, middle);
            MergeSort(array, middle + 1, right);
            Merge(array, left, middle, right);
        }

        // 合并两个子序列
        public static void Merge(int[] array, int left, int middle, int right)
        {
            int[] temp = new int[right - left + 1];
            int index = 0, lindex = left, rindex = middle + 1;
            while (lindex <= middle && rindex <= right)
            {
                if (array[rindex] < array[lindex])
                {
                    temp[index++] = array[rindex++];
                }
                else
                {
                    temp[index++] = array[lindex++];
                }
            }
            while (lindex <= middle)
            {
                temp[index++] = array[lindex++];
            }
            while (rindex <= right)
            {
                temp[index++] = array[rindex++];
            }

            while (--index >= 0)
            {
                array[left + index] = temp[index];
            }
        }
}