Author:龙箬
Computer Application Technology
Change the World with Data and Artificial Intelligence !
CSDN@weixin_43975035
帘外桃花开仍旧，帘内人比桃花瘦

n\sqrt{n}n​ 段合并排序算法：

• 如果在归并排序算法的分割步骤中，将数组 a[0:n−1]a[0:n-1]a[0:n−1]划分为 ⌊n⌋\lfloor \sqrt{n} \rfloor⌊n​⌋
  个子数组，每个子数组中有 O(n)O(\sqrt{n})O(n​) 个元素，然后递归的对分割后的子数组进行排序。最后将所得到的 ⌊n⌋\lfloor \sqrt{n} \rfloor⌊n​⌋ 个排好序的子数组归并成排好序的数组 a[0:n−1]a[0:n-1]a[0:n−1]。
• 设计一个实现上述策略的归并排序算法，并分析算法的计算复杂性。

Java程序代码如下：

package com.company;public class MERGESORT {public static void main(String[] args) {int[] a = {8, 13, 52, 34, 57, 47, 96, 905, 28, 12, 44, 176}; mergesort(a, 0, a.length - 1);for (int k : a) {System.out.print(k + ",");}}private static void merge(int[] a, int i, int n1, int j, int n2) {int tmpi = i;int k = i;int[] p = new int[a.length];//临时数组while (i <= n1 && j <= n2) {if (a[i] < a[j])p[k++] = a[i++];elsep[k++] = a[j++];}while (i <= n1)p[k++] = a[i++];while (j <= n2)p[k++] = a[j++];for (int o = tmpi; o <= n2; o++)a[o] = p[o];}public static void mergesort(int[] a, int left, int right) {if (left == right)return;int sqrt = (int) Math.sqrt(right - left + 1);for (int i = left, j = left; i <= right; i = j + 1) {j = Math.min(i + sqrt - 1, right);mergesort(a, i, j);if (i != left)merge(a, left, i - 1, i, j);}}

伪代码如下：

procedure mergesort(a[],low, high)//a(low: high)是一个全程数组，low和high分别指示当前待排序区间的最小下标和最大下标，它含有high-low+1≥0个待排序的元素integer low, high, i, jsqrt <- (int)Math.sqrt(right-left+1) //计算根号n分界点for(i=left, j=left; i<=right; i=j+1){j = Math.min(i + sqrt - 1, right);//计算每一个子集合结束位置mergesort(a, i, j);//递归调用每一个子集合排序if (i != left)merge(a, left, i - 1, i, j); //与其前一个子集合合并}
end mergesortprocedure merge(a[], int i, int n1, int j, int n2)  //使用辅助数组归并两个已排序的集合int tmpi <- i;int k <- i;int[] p = new int[a.length];//临时数组while (i <= n1 && j <= n2) { //处理处理两个已排序的序列，当两个集合都没有取尽时,将较小的元素先存放到P中if (a[i] < a[j]) //如果前一个数组中的元素较小p[k++] <- a[i++];else  //如果后一个数组中的元素较小p[k++] <- a[j++];}while (i <= n1)  //剩余元素处理过程p[k++] <- a[i++];while (j <= n2) //剩余元素处理过程p[k++] <- a[j++];for o <-tmpi to do a[o] <- p[o] repeat //将已排序的集合复制到a数组
end merge

时间复杂度：

T(n)=n1/2⋅T(n1/2)+O(n)T(n) =n^{1/2}·T(n^{1/2})+O(n)T(n)=n1/2⋅T(n1/2)+O(n)

T(n1/2)=n1/4⋅T(n1/4)+O(n1/2)T(n^{1/2}) =n^{1/4}·T(n^{1/4})+O(n^{1/2})T(n1/2)=n1/4⋅T(n1/4)+O(n1/2)

T(n1/4)=n1/8⋅T(n1/8)+O(n1/4)T(n^{1/4}) =n^{1/8}·T(n^{1/8})+O(n^{1/4})T(n1/4)=n1/8⋅T(n1/8)+O(n1/4)
T(n)=n1/2[n1/4⋅T(n1/4)+O(n1/2)]+O(n)=n1/2+1/4⋅T(n1/4)+n1/2⋅O(n1/2)+O(n)=......=n1/2+1/4+1/8+...+1/2x⋅T(n1/2x)+n1/2x−1⋅O(n1/2x−1)+...+n1/2⋅O(n1/2)+O(n)<=n⋅T(1)+n1/2x−1⋅O(n1/2x−1)+...+n1/2⋅O(n1/2)+O(n)\begin{aligned} T(n) &=n^{1/2}[n^{1/4}·T(n^{1/4})+O(n^{1/2})]+O(n)\\ &=n^{1/2+1/4}·T(n^{1/4})+n^{1/2}·O(n^{1/2})+O(n)\\ &=......\\ &=n^{1/2+1/4+1/8+...+1/2^{x}}·T(n^{1/2^{x}})+n^{1/2^{x-1}}·O(n^{1/2^{x-1}})+...+n^{1/2}·O(n^{1/2})+O(n)\\ &<=n·T(1)+n^{1/2^{x-1}}·O(n^{1/2^{x-1}})+...+n^{1/2}·O(n^{1/2})+O(n) \end{aligned} T(n)​=n1/2[n1/4⋅T(n1/4)+O(n1/2)]+O(n)=n1/2+1/4⋅T(n1/4)+n1/2⋅O(n1/2)+O(n)=......=n1/2+1/4+1/8+...+1/2x⋅T(n1/2x)+n1/2x−1⋅O(n1/2x−1)+...+n1/2⋅O(n1/2)+O(n)<=n⋅T(1)+n1/2x−1⋅O(n1/2x−1)+...+n1/2⋅O(n1/2)+O(n)​

n⋅O(n)=O(n)\sqrt{n}·O(\sqrt{n}) =O(n)n​⋅O(n​)=O(n) 且 n1/2x−1⋅O(n1/2x−1)​⋅O(n​)

故原式 T(n)<=n⋅T(1)+n⋅logn=O(n⋅logn)T(n) <= n·T(1) + n· log n =O(n·log n)T(n)<=n⋅T(1)+n⋅logn=O(n⋅logn)

空间复杂度：
归并时用 minminmin 堆来存储每个组当前的最小值
T(n)=n⋅T(n)+c(n−1)⋅lognT(n)=\sqrt{n}·T(\sqrt{n})+c(n-1)·log\sqrt{n}T(n)=n​⋅T(n​)+c(n−1)⋅logn​

参考致谢：
国科大 马丙鹏老师《计算机算法设计与分析》

如有侵权，请联系侵删
需要本实验源数据及代码的小伙伴请联系QQ:2225872659