问题描述

归并排序是一种基于分治策略的排序算法，它将待排序的数列不断拆分成较小的子序列，直到每个子序列只包含一个元素，然后将相邻的子序列进行合并，最终得到有序的数列。

问题分析

归并排序的核心是将两个有序的子序列合并成一个有序的序列。具体实现时，可以通过递归地将待排序数列不断拆分，直到每个子序列只包含一个元素，然后将相邻的子序列进行合并。在合并过程中，可以使用一个辅助数组，将两个有序的子序列合并到该数组中，再将该数组中的元素复制回原数组的对应位置。

代码实现

下面是使用C语言实现归并排序的代码：

使用上面的C语言代码实现归并排序后，可以得到以下输出结果：

以上输出结果表示经过归并排序后，原先无序的数组已经按照从小到大的顺序排列好了。

时间复杂度分析

merge()函数的时间复杂度分析：

• 此函数的时间复杂度取决于while循环的迭代次数，即比较左右两个子数组元素并将较小者放入合并后的数组中；

• 最坏情况下，左右两个子数组中每个元素都需要比较一次，因此while循环的迭代次数为left_len + right_len，即O(n)；

• 而此函数中还有两个while循环，用于将未被比较完的子数组中的剩余元素放入合并后的数组中，其时间复杂度为O(left_len)和O(right_len)，故不影响总体时间复杂度。

merge_sort()函数的时间复杂度分析：

• 此函数是递归实现的，当数组长度小于等于1时直接返回，故其时间复杂度为O(1)；

• 在每次递归中，先将原数组分成左右两个子数组，时间复杂度为O(n)；

• 接着分别对左右两个子数组进行递归调用merge_sort()函数，此时原数组长度被分为一半，故递归深度为log2(n)，而每层递归都需要对原数组中的每个元素进行操作，因此总体时间复杂度为O(nlogn)。

综上所述，归并排序的时间复杂度为O(nlogn)。

至此，归并排序结束。