Merge Sort

假設有一陣列 [8, 4, 5, 7, 1, 3, 6, 2]，會先將陣列每次拆分成兩組同大小的子陣列，直到每組都只有一個元素再進行排序後合併。

internal class Program
{
    private static void Main(string[] args)
    {
        int[] ary = new int[5];    //宣告陣列大小為10

        Random rnd = new Random();  //產生亂數初始值

        for (int i=0; i<ary.Length; i++)
        {
            ary[i] = rnd.Next(1, 10);   //亂數產生，亂數產生的範圍是1~9
        }

        Console.WriteLine("原始陣列內容：");
        showArray(ary);

        MergeSort(ary);

        Console.WriteLine("由小到大排序後陣列內容：");
        showArray(ary);
    }

    static void MergeSort(int[] ary)
    {
        System.Diagnostics.Stopwatch stopWatch = new System.Diagnostics.Stopwatch();
        stopWatch.Start();  //計算程式時間開始

        int[] temp = new int[ary.Length];   //暫存用陣列
        int loop = 1;
        int counter = 0;

        //2個一組比較排序，4個一組排序，8個一組排序，依此類推...
        for(int size=1; size < ary.Length; size *= 2)
        {
            for(int left=0; (left+size) < ary.Length; left += size*2)
            {
                int mid = left + size;
                int right = mid + size;

                if (right > ary.Length) right = ary.Length;

                int index = left;   //temp陣列起始位置
                int i = left;
                int j = mid;

                //組合併
                while(i < mid && j < right)
                {
                    if (ary[i] < ary[j])
                    {
                        temp[index] = ary[i];
                        i++;
                    }
                    else
                    {
                        temp[index] = ary[j];
                        j++;
                    }
                    index++;
                }

                //將未處理的陣列數值依序存入temp陣列
                //以下兩個while只會執行一個
                while(i < mid)
                {
                    temp[index] = ary[i];
                    i++;
                    index++;
                }

                while(j < right)
                {
                    temp[index] = ary[j];
                    j++;
                    index++;
                }

                //將暫存已排好的資料，寫回原本陣列
                for(int m=left; m < right; m++)
                {
                    ary[m] = temp[m];
                }

                counter++;
            }

            Console.Write($"第{loop}輪結果:");
            showArray(ary);
            loop++;
        }

        Console.WriteLine("執行次數:" + counter);

        stopWatch.Stop();   //計算程式時間結束
        Console.WriteLine("程式執行時間(秒)：" + (stopWatch.Elapsed.TotalMilliseconds / 1000));
    }

    //兩個值互相交換
    static void swap(int[] ary, int value1, int value2)
    {
        int tmp = ary[value2];
        ary[value2] = ary[value1];
        ary[value1] = tmp;
    }

    //顯示陣列內容
    static void showArray(int[] ary)
    {
        for (int i=0; i<ary.Length; i++)
        {
            Console.Write(ary[i] + ",");
        }
        Console.WriteLine();
    }
}