归并排序:二路归并（稳定）

基本思想:
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

【 算法思想 】 假设初始序列含有 n 个记录，首先将这 n 个记录看成 n 个有序的子序列，

每个子序列的长度为 1，然后两两归并，得到 n/2个长度为 2（n 为奇数时，最后一
个序列的长度为 1）的有序子序列；
在此基础上，再对长度为 2 的有序子序列进行两两归并，得到若干个长度为 4 的有
序子序列；如此重复，直至得到一个长度为 n 的有序序列为止。这种方法被称作 2-路归并排序。

二路归并

---

C# 实现：

递归方式：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

/// <summary>
/// 归并排序
/// </summary>
public class MergeSort
{
    
    /// <summary>
    /// 递归分治
    /// </summary>
    /// <param name="a"></param>
    /// <param name="left"></param>
    /// <param name="right"></param>
    public static void SortRecusion(int[] a,int left,int right)
    {
        if (left >= right)
        {
            return;
        }
        int mid = (left + right) / 2;

        SortRecusion(a, left, mid);
        SortRecusion(a, mid + 1, right);
        Merge(a, left, mid, right);        
    }

    /// <summary>
    /// 合并
    /// </summary>
    /// <param name="a"></param>
    /// <param name="left"></param>
    /// <param name="mid"></param>
    /// <param name="rigth"></param>
    public static void Merge(int[] a,int left,int mid,int rigth)
    {
        int[] temp = new int[rigth - left + 1];//中间数组

        int i = left;//左开头
        int j = mid + 1;//右开头

        int k = 0;
        while(i<=mid&&j<=rigth)//把较小的数先移到新数组中
        {
            if(a[i]<=a[j])
            {
                temp[k++] = a[i++];
            }
            else
            {
                temp[k++] = a[j++];
            }
        }
        // 把左边剩余的数移入数组
        while (i<=mid)
        {
            temp[k++] = a[i++];
        }
        // 把右边边剩余的数移入数组
        while (j <= rigth)
        {
            temp[k++] = a[j++];
        }

        // 把新数组中的数覆盖nums数组
        for (int p=0;p<temp.Length;p++)
        {
            a[left + p] = temp[p];
        }



    }
}

---

非递归方式:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

/// <summary>
/// 归并排序
/// </summary>
public class MergeSort
{



    /// <summary>
    /// 非递归
    /// </summary>
    /// <param name="a"></param>
    /// <param name="length"></param>
    public static void SortIteration(int[] a, int length)
    {
        for (int gap = 1; gap < length; gap = 2 * gap)
        {
            MergePass(a, gap, length);
        }
    }

    public static void MergePass(int[] a, int gap, int length)
    {
        int i = 0;
        //归并 gap 长度的两个相邻子表
        for (i = 0; i + 2 * gap - 1 < length; i += 2 * gap)
        {
            Merge(a, i, i + gap - 1, i + 2 * gap - 1);
        }
        //余下两个子表，后者长度小于gap
        if (i + gap - 1 < length)
        {
            Merge(a, i, i + gap - 1, length - 1);
        }
    }

    /// <summary>
    /// 合并
    /// </summary>
    /// <param name="a"></param>
    /// <param name="left"></param>
    /// <param name="mid"></param>
    /// <param name="rigth"></param>
    public static void Merge(int[] a, int left, int mid, int rigth)
    {
        int[] temp = new int[rigth - left + 1];//中间数组

        int i = left;//左开头
        int j = mid + 1;//右开头

        int k = 0;
        while (i <= mid && j <= rigth)//把较小的数先移到新数组中
        {
            if (a[i] <= a[j])
            {
                temp[k++] = a[i++];
            }
            else
            {
                temp[k++] = a[j++];
            }
        }
        // 把左边剩余的数移入数组
        while (i <= mid)
        {
            temp[k++] = a[i++];
        }
        // 把右边边剩余的数移入数组
        while (j <= rigth)
        {
            temp[k++] = a[j++];
        }

        // 把新数组中的数覆盖nums数组
        for (int p = 0; p < temp.Length; p++)
        {
            a[left + p] = temp[p];
        }

    }

}

---

测试用例：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;


public class _015_MergeSort : MonoBehaviour
{


    void Start()
    {
        int[] a = Utilit.RandArray(20, 10);

        int[] b = (int[])a.Clone();

        Debug.Log("---------------归并排序:递归--------------");
        MergeSort.SortRecusion(a, 0, a.Length - 1);
        Utilit.Print(a, 0);

        Debug.Log("---------------归并排序:非递归--------------");
        MergeSort.SortIteration(b, b.Length);
        Utilit.Print(b, 0);
    }


}

---

测试结果：

img.jpg

---

注：

整个归并排序需进行 m（m=log 2 n）趟 2-路归并，所以归并排序总的时间复杂度为 O（nlog 2 n）。在实现归并排序时，需要和待排记录等数量的辅助空间，空间复杂度为O(n)。

类似 2-路归并排序，可设计多路归并排序法。与快速排序和堆排序相比，归并排序
的最大特点是，它是一种稳定的排序方法。一般情况下，由于要求附加和待排记录等数
量的辅助空间，因此很少利用 2-路归并排序进行内部排序，归并的思想主要用于外部排序。

外部排序可分两步:
①待排序记录分批读入内存，用某种方法在内存排序，组成有序的子文件，再按某种策略存入外存。
②子文件多路归并，成为较长有序子文件，再进入外存，如此反复，直到整个待排序文件有序。
外部排序可使用磁带、磁盘等外存，最初形成有序子文件长取决于内存所能提供排序区大小和最初排序策略，归并路数取决于能提供排序的外部设备数。

image.png