C#中自顶向下的归并排序实现

using System;

class MergeSort
{
    // 归并排序入口函数
    public static void Sort(int[] arr)
    {
        int[] temp = new int[arr.Length];
        Sort(arr, temp, 0, arr.Length - 1);
    }

    // 递归地对数组进行分割和合并
    private static void Sort(int[] arr, int[] temp, int left, int right)
    {
        if (left >= right)
            return;

        int mid = (left + right) / 2;
        Sort(arr, temp, left, mid); // 对左半部分进行排序
        Sort(arr, temp, mid + 1, right); // 对右半部分进行排序
        Merge(arr, temp, left, mid, right); // 合并左右两部分
    }

    // 合并两个有序数组
    private static void Merge(int[] arr, int[] temp, int left, int mid, int right)
    {
        int i = left; // 左半部分起始索引
        int j = mid + 1; // 右半部分起始索引
        int k = left; // 合并后数组的起始索引

        // 将两个有序数组合并到临时数组中
        while (i <= mid && j <= right)
        {
            if (arr[i] <= arr[j])
            {
                temp[k++] = arr[i++];
            }
            else
            {
                temp[k++] = arr[j++];
            }
        }

        // 将剩余的元素复制到临时数组中
        while (i <= mid)
        {
            temp[k++] = arr[i++];
        }
        while (j <= right)
        {
            temp[k++] = arr[j++];
        }

        // 将临时数组中的元素复制回原数组
        for (int m = left; m <= right; m++)
        {
            arr[m] = temp[m];
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        int[] arr = { 9, 5, 7, 2, 4, 1, 6, 8, 3 };
        MergeSort.Sort(arr);

        Console.WriteLine("排序结果：");
        foreach (int num in arr)
        {
            Console.Write(num + " ");
        }
    }
}