Time complexity:O(logn)
方法:二路归并(2-way merge)
对象:有序序列(sorted sequence), 即可以是有序向量(sorted vector),也可以是列表(list)算法性质:迭代
步骤: 1.无序向量的递归分解(递归) 2.有序序列的逐层归并(迭代)
算法描述:(摘自Oxford一哥们写的DS教材~)
“Divide and conquer ” Merge sort has three steps to sort an input sequence S with n elements:
Divide—partition S into two sequences S1 and S2 of about n/2 elements each Recur—recursively sort S1 and S2Conquer—merge S1 and S2 into a sorted sequence