XIAOSUO 记录个人学习的足迹

对于排序大列表数据，一个有效的排序算法是归并排序。类似于快速排序算法，其使用的是分治法来排序。归并排序的基本思想是：将两个或两个以上的有序子序列”归并”为一个有序序列。在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列“归并”为一个有序序列。
一、基本思想

　　二路归并排序的基本思想是：将有n个记录的原始序列看作n个有序子序列，每个子序的长度为1，然后从第一个子序列开始，把相邻的子序列两两合关，得到n/2个长度为2或1的子序列（当子序列的个数为奇数时，最后一组合并得到的序列长度为1），我们把这一过程称为一次归并排序，对一次归并排序的n/2个子序列采用上述方法继续顺序成对归并，如此重复，当最后得到长度为n的一个子序列时，该子序列便是原始序列归并排序后的有序序列。

　　　　　　
　　　　第一步，将列表中的11个元素看成11个有序的序列，每个子序列的长度为1，然后两两归并，得到5个长度为2和1个长度为1的有序子序列。
　　　　第二步，将6个有序子序列两两归并，得到2个长度为4和1个长度为3的有序子序列。
　　　　第三步，将2个长度为4的有序子序列归并，得到第三趟归并结果。
　　　　第四步，将长度为8有序子序列和长度为3的有序子序列归并，得到第四趟归并结果，是长度为11的一个有序子序列。

二、并归排序的实现

public class MergeSort
{
    //P=NP:
    public static List<int> Demo(List<int> data)
    {
        var arr = data.ToArray();
        if (data.Count < 2)
        {
            return data;
        }
        int middle = (int)Math.Floor(((decimal)(data.Count / 2)));
        var left = arr.AsSpan().Slice(0, middle).ToArray();
        var right = arr.AsSpan().Slice(middle).ToArray();
        return Merge(Demo(left.ToList()), Demo(right.ToList()));
    }

    static List<int> Merge(List<int> left, List<int> right)
    {
        var result = new List<int>();

        while (left.Count > 0 && right.Count > 0)
        {
            if (left[0] <= right[0])
            {
                result.Add(left[0]);
                left.RemoveAt(0);
            }
            else
            {
                result.Add(right[0]);
                right.RemoveAt(0);
            }
        }

        while (left.Count != 0)
        {
            result.Add(left[0]);
            left.RemoveAt(0);
        }


        while (right.Count != 0)
        {

            result.Add(right[0]);
            right.RemoveAt(0);
        }

        return result;
    }
}

三、时间复杂度分析

　　二路归并排序的时间复杂度为O(nlog2n)。
　　二路归并排序算法的空间复杂度为O(n)。