√n段合并排序算法 时间复杂

√n段合并排序算法的时间复杂度为O(nlogn)。

合并排序算法是一种经典的分治算法，它的基本思想是将待排序的数组分成多个子数组，然后对每个子数组递归地进行排序，最后再将排好序的子数组合并成一个有序的数组。

在√n段合并排序算法中，我们首先将待排序的数组分成√n个子数组，每个子数组的长度是n/√n=n^(1/2)。然后对每个子数组使用其他排序算法，如插入排序、快速排序等进行排序。

对于每个子数组的排序算法，时间复杂度是O((n/√n)log(n/√n))=O(n/√n * log(n/√n))=O(n^(1/2) * 2logn)=O(n^(1/2)logn)。

最后，将排好序的子数组进行合并，合并过程的时间复杂度是O(n)。

因此，总的时间复杂度为O(√n * n^(1/2)logn + n)=O(n^(3/2)logn)。

综上所述，√n段合并排序算法的时间复杂度为O(n^(3/2)logn)。