Sequential Mergesort
func mergesort(A) |A| = n
if n <= 1 return A
(spawn)
A1 = mergesort(A[1:n/2])
A2 = mergesort(A[n/2+1:n])
(sync)
return merge(A1,A2)
- work optimality(right)
- polylog span(no)
那么应该如何提高效率呢？
我们可以看见这个算法的主要限制是merge的过程是顺序的，所以限制了算法的速度。那么有什么方式可以提高效率呢？
image
其实我们可以用在 A 序列中找到一个终点，并用它将 B 分成两部分使得
那么在最理想的情况下我们可以得到 ,其中 log n 是二分查找 B的重点的过程。
在最坏的情况下，是 与
merge的
