归并排序

数据

• 平均时间复杂度：O(nlogn)

• 最好时间复杂度：O(nlogn)

• 最坏时间复杂度：O(nlogn)

• 空间复杂度：O(n)

• 排序方式：Out-Place

• 稳定性：稳定

描述

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

动图

C#实现

public class MergeSort
{
    public static void Sort<T>(IList<T> list, Func<T, T, bool> compare)
    {
        var count = list.Count;
        if (count < 2)
        {
            return;
        }

        IList<T> newList = new List<T>(count);
        for (int size = 1; size < count; size += size)
        {
            for (int start = 0; start < count; start += size + size)
            {
                var low = start;
                var mid = Math.Min(start + size - 1, count - 1);
                var high = Math.Min(start + size + size - 1, count - 1);

                InternalMergeSort(list, low, mid, high, compare);
            }
        }
    }

    public static void InternalMergeSort<T>(IList<T> list, int low, int mid, int high, Func<T, T, bool> compare)
    {
        IList<T> newList = new T[high - low + 1];

        var leftStart = low;
        var leftEnd = mid;
        var rightStart = mid + 1;
        var rightEnd = high;

        var index = 0;
        while (leftStart <= leftEnd && rightStart <= rightEnd)
        {
            if (compare(list[leftStart], list[rightStart]))
            {
                newList[index++] = list[leftStart++];
            }
            else
            {
                newList[index++] = list[rightStart++];
            }
        }

        while (leftStart <= leftEnd)
        {
            newList[index++] = list[leftStart++];
        }

        while (rightStart <= rightEnd)
        {
            newList[index++] = list[rightStart++];
        }

        index--;
        while (index >= 0)
        {
            list[rightEnd--] = newList[index--];
        }
    }
}

Lua实现