自研O(log(n))空间归并排序变体是否为全新排序算法？

改进目标 #

我尝试对归并排序进行改进，达成以下目标：

• 将空间复杂度降至O(log(n))
• 最优时间复杂度优化为O(n)
• 同时保持稳定性与O(n log(n))的最坏时间复杂度

C#实现代码 #

public static void mergeSortMineInit(List<int> list)
{
    int n = list.Count;
    int width = 32;

    for (int i = 0; i <= n; i += width)
    {
        insertionSortModified(list, i, Math.Min(i + width, n));
    }

    while (width <= n)
    {
        int width2T = 2 * width;

        for (int i = 0; i <= n; i += width2T)
        {
            merge(list, i, Math.Min(i + width, n - 1), Math.Min(i + width2T, n));
        }

        width = width2T;
    }
}

public static void insertionSortModified(List<int> arr, int startIndex, int endIndex)
{
    for (int i = startIndex + 1; i < endIndex; i++)
    {
        int key = arr[i];
        int j = i - 1;

        while (startIndex <= j && key < arr[j])
        {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }
}

public static void merge(List<int> list, int start, int mid, int end)
{
    int? amountOfItems = kthElementAmount(
      list: list,
      start: start,
      midEnd: mid,
      mid: mid,
      end: end
    );

    if (amountOfItems == null)
    {
        return;
    }

    int newMidIndex = mid - amountOfItems.Value;
    int i = newMidIndex;
    int j = mid;

    for (; j < mid + amountOfItems; i++, j++)
    {
        int temp = list[j];
        list[j] = list[i];
        list[i] = temp;
    }

    merge(list, start, newMidIndex, mid); //m-amount,m
    merge(list, mid, mid + amountOfItems.Value, end); //amount,n
}

public static int? kthElementAmount(List<int> list, int start, int midEnd, int mid, int end, bool isNormal = true)
{
    int list1Size = midEnd - start;
    int list2Size = end - mid;

    if (Math.Min(list1Size, list2Size) <= 16)
    {
        miniSort(list: list, start: start, mid: mid, end: end);
        return null;
    }

    if (list1Size > list2Size)
    {
        return kthElementAmount(list: list, start: mid, midEnd: end, mid: start, end: midEnd, isNormal: false);
    }

    int k = isNormal ? list1Size : list2Size;

    int low = 0;
    int high = list1Size;

    Func<int?, int?, bool> l1r2Func;
    Func<int?, int?, bool> l2r1Func;

    if (isNormal)
    {
        l1r2Func = (l1, r2) => l1 == null || r2 == null || l1 <= r2;
        l2r1Func = (l2, r1) => l2 == null || r1 == null || l2 < r1;
    }
    else
    {
        l1r2Func = (l1, r2) => l1 == null || r2 == null || l1 < r2;
        l2r1Func = (l2, r1) => l2 == null || r1 == null || l2 <= r1;
    }

    while (low <= high)
    {
        int cut = (low + high) >> 1;
        int cut1 = cut + start;
        int cut2 = (k - cut) + mid;

        int? l1Index = cut1 == start ? null : cut1 - 1;

        int? l1 = l1Index == null ? null : list[l1Index.Value]; //MIN_VALUE
        int? r1 = cut1 == midEnd ? null : list[cut1]; //MAX_VALUE

        //
        int? l2Index = cut2 == mid ? null : cut2 - 1;
        int? l2 = l2Index == null ? null : list[l2Index.Value]; //MIN_VALUE
        int? r2 = cut2 == end ? null : list[cut2]; //MAX_VALUE

        bool l1r2Bool = l1r2Func(l1, r2);
        bool l2r1Bool = l2r1Func(l2, r1);

        if (l1r2Bool && l2r1Bool)
        {
            if (isNormal)
            {
                return l2Index == null ? null : l2Index - mid + 1; //amount
            }
            else
            {
                return l1Index == null ? null : l1Index - start + 1; //amount
            }
        }
        else if (!l1r2Bool)
        {
            high = cut - 1;
        }
        else
        {
            low = cut + 1;
        }
    }
    throw new Exception("Incorrect input??!!");
}

public static void miniSort(List<int> list, int start, int mid, int end)
{
    List<int> tempList = new List<int>();
    if (start > mid)
    {
        return;
    }
    if (end - mid < mid - start)
    {
        //second smaller
        for (int j = mid; j < end; j++)
        {
            tempList.Add(list[j]);
        }

        int listIndex = mid - 1;
        int tempIndex = tempList.Count - 1;

        int counter = end - 1;

        for (; start <= listIndex && 0 <= tempIndex; counter--)
        {
            if (tempList[tempIndex] < list[listIndex])
            {
                list[counter] = list[listIndex];
                listIndex--;
            }
            else
            {
                list[counter] = tempList[tempIndex];
                tempIndex--;
            }
        }

        for (; start <= listIndex; counter--)
        {
            list[counter] = list[listIndex];
            listIndex--;
        }

        for (; 0 <= tempIndex; counter--)
        {
            list[counter] = tempList[tempIndex];
            tempIndex--;
        }
    }
    else
    {
        //first smaller
        for (int i = start; i < mid; i++)
        {
            tempList.Add(list[i]);
        }

        int tempListSize = tempList.Count;

        int listIndex = mid;
        int tempIndex = 0;

        int counter = start;

        for (; listIndex < end && tempIndex < tempListSize; counter++)
        {
            if (tempList[tempIndex] <= list[listIndex])
            {
                list[counter] = tempList[tempIndex];
                tempIndex++;
            }
            else
            {
                list[counter] = list[listIndex];
                listIndex++;
            }
        }

        for (; listIndex < end; counter++)
        {
            list[counter] = list[listIndex];
            listIndex++;
        }

        for (; tempIndex < tempListSize; counter++)
        {
            list[counter] = tempList[tempIndex];
            tempIndex++;
        }
    }
}

性能测试结果 #

测试基于3000000条数据：

随机元素 #

• Top Down Merge Sort: 0:00:01.322298
• Bottom Up Merge Sort: 0:00:01.794660
• MergeSort Mine: 0:00:03.539161
• Heap Sort: 0:00:04.485955

已排序元素 #

• Top Down Merge Sort: 0:00:00.448717
• Bottom Up Merge Sort: 0:00:00.682326
• Merge Sort Mine: 0:00:00.105623
• Heap Sort: 0:00:01.298882

原创性分析 #

你的算法核心思路属于**原地归并排序（In-place Merge Sort）**的优化变体，并非完全原创的新算法，这类思路在排序算法研究中已有同类方案：

1. 空间复杂度优化到O(logn)：
   你通过递归分治+原地交换的方式替代传统归并的额外数组拷贝，这和原地归并排序的核心思路一致——利用分治递归的栈空间（O(logn)）来避免传统归并所需的O(n)额外空间，这类算法在1990年代就有相关研究实现。

2. 最优时间复杂度O(n)：
   你先对小分段用插入排序预处理，再在归并前判断有序性提前终止，这借鉴了Timsort、IntroSort等混合排序的思路——对部分有序数据做针对性优化，让已排序或接近有序的数据达到线性时间处理。

3. 稳定性保持：
   你的交换和归并逻辑维持了相等元素的相对顺序，这也是原地归并排序中常见的设计目标，已有同类稳定原地归并方案实现了这一点。

你的测试结果中已排序数据的优异表现，正是因为提前识别了有序段并跳过了不必要的归并操作，这和Timsort的"奔跃模式"有相似的优化方向，但具体实现细节有差异。

整体来看，你的算法是对现有原地归并排序和混合排序思路的组合优化，虽然实现细节有自己的设计，但核心优化方向并非全新的原创思路。

内容的提问来源于stack exchange，提问作者Majd AL-Shalash