- 一、问题描述
- 二、分治策略
- 三、算法举例
- 四、复杂度
应用归并排序方法对一个规模为n的记录序列进行升序排序.
排序数组a[0:n-1]
待排序区间[left,right]
1）划分：
将要排序序列划分为两个长度大致相等的子序列
如果,left=right只有一个，无需排序，算法结束
否则,计算划分中的:mid=(left+right)/2
2）求解子问题
对前半个子序列a[0]~a[mid]进行升序排序
对后半个子序列a[mid+1]~a[right]进行升序排序
3）合并
归并两个有序子序列合成一个有序序列。
时间复杂度始终是O（nlog2n）
空间复杂度为O（n）
