自底向上归并排序的实现

Question

我了解到归并排序是一种遵循分而治之原则的排序算法，平均时间复杂度为n(log n)。

在这里，我将大小为n的数组划分为子数组（初始化为长度2），并通过对子数组进行排序来征服它。然后我们以 2 的倍数继续范围，直到它小于数组的长度（即 2,4,8,....i，其中 i<数组的长度）。

当它超过数组的长度时，函数return排序数组。

我用过两个函数来实现归并排序：

归并排序（生成子数组）

如果数组的长度小于return数组的范围。
递归并以指数方式增加范围。

插入排序（对子数组排序）

使用插入排序对范围内的元素进行排序。我选择了插入排序，因为它比冒泡排序和选择排序更有效。

程序运行良好，我想知道我是否理解并正确实现了归并排序的概念？

//C++ Code
#include<iostream>

// Print
void print(int *arr, int length);

// To Sort the sub array
void insertion_sort(int *arr, int low, int high)
{
    for(int i = high; (i-1)>=low; i--)
    {
        if (arr[i] < arr [i-1])
        {
            int temp = arr[i];
            arr[i] = arr[i-1];
            arr[i-1] = temp;
        }
    }
}

int *merge_sort(int* arr, int length, int index = 2)
{
    if (length <= index) // Terminating Condition
    {
        return arr;
    }

    // The range is defined by index.

        /*
            If array has 8 elements:  ********
            It will sort array until it's range within the length of array.
            1st call  2*1 elements max: ** ** ** ** // 2 set as default argument
            2nd call  2*2 elements max: **** ****
            3rd call  2*3 elements max: ********
            Returns Array
        */

    // The range is defined by index.

    for(int i=0; (i+index)<length; i+=index)
    {
        // Divide and Sort
        insertion_sort(arr, i, i+index);
    }

    // The range will increase in multiple of 2 (i.e. 2,4,8,....i where i<length of array)
    return merge_sort(arr, length, index*2);
}

int main()
{
    int length;    
    std::cout<<"Length of Array: ";
    std::cin>>length;

    int arr[length];

    for(int i=0; i<length; i++)
    {
        std::cout<<"Enter element "<<i+1<<" : ";
        std::cin>>arr[i];
    }

    int *result = merge_sort(arr, length);
    
    print(result, length);
    
    return 0;
}

void print(int *arr, int length)
{
    std::cout<<"Sorted Array: ";

    for(int i=0; i<length; i++)
    {
        std::cout<<arr[i]<<" ";
    }

    std::cout<<"\n";
}

Answer 1

纯自下而上的归并排序将 n 个元素的数组分成 n 运行个大小为 1 的数组，然后每遍合并偶数和奇数运行个。 Link 到 wiki 示例：

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation

正如 Wiki 示例评论中所建议的，每次通过都可以更改合并的方向。要以原始数组中的排序数据结束，请计算所需的遍数，如果遍数为奇数，则比较并交换（如果需要）元素对以创建大小为 2 的运行s ，然后进行合并排序。

对于混合插入+归并排序，对遍数做同样的计算，如果遍数为奇数，则设置初始运行大小为32个元素，否则设置初始运行大小为 64 个元素。使用插入排序对初始运行进行一次排序，然后切换到归并排序。

获取通过次数的简单示例代码（对于 32 位版本，假设 n <= 2^31）：

size_t GetPassCount(size_t n)               // return # passes
{
    size_t i = 0;
    for(size_t s = 1; s < n; s <<= 1)
        i += 1;
    return(i);
}

自底向上归并排序的实现

Implementation of Bottom Up Merge Sort

c++

arrays

algorithm

mergesort