二路归并排序,二分归并排序算法

一、伪代码

1.      MergeSort(A,l,r)

2.      Merge(A,l,m,r) 

 

 

 

二、C/C++代码 

/******************************************************************* 

Function:MergeDescription:将两个有序的数组A[l,m]和A[m+1,r]合并为一个有序的数组Input:数组A及下标l，m，rOutput:有序数组A********************************************************************/void Merge(int A[],int l,int m,int r){ int x = m-l+1,y=r-m;//x表示数组A[l...m]的长度，y表示数组A[m+1,r]的长度 int *B = new int[x]; int *C = new int[y]; for(int i=0,j=l;i=x) while(j 

三、时间复杂度

 

由分治的思想知，对一个数组排序可以转换为将原数组一分为二，各种排序后在合并的过程。设该算法的最坏时间复杂度为W(n)，则递推公式如下：

其中n-1是将两个有序数组合并成一个有序数组的时间复杂度。

 

解法一：

 

解法二：

利用https://blog.csdn.net/bqw18744018044/article/details/79596014中介绍的主定理。