MergeSort

MergeSort is the first deterministic sort algorithm whose time conplexity is .

template <typename T>
void vector<T>::MergeSort(Rank lo,Rank hi)
{
	if(hi-lo<2)  return;
	int mi=(lo+hi)/2;
	MergeSort(lo,mi);
	Mergesor(mi,hi);
	merge(lo,mi,hi);
}
template <typename T>
void vector<T>::merge(Ran lo,Rank mi,Rank hi)
{
	T*A=_elem+lo;
	int lb=mi-lo;
	T* B=new T[lb];
	for(Rank i=0;i<lb;B[i]=A[i++];) ;          //复制前子向量[WHY?] 
	int lc=hi-mi;
	T* C=_elem+mi;                             //[WHY?]
	for(Rank i=0,j=0,k=0;(j<lb||k<lc);)
	{
		if((j<lb)&&(!(k<lc)||(B[j]<=C[k]))) A[i++]=B[j++];
		if((k<lc)&&(!(j<lb)||(C[k]<B[j])))  A[i++]=C[k++];
	}
	delete [] B;
}

---

Complexity Analysis

Easily find that costs not more than .
So, if denotes the time cost of MergeSort, we have

$$T(n)=2*T(n/2)+\mathcal{O}(n) \\ T(1)=\mathcal{O}(1)$$

Hence,

$$T(n)/n=T(n/2)/(n/2)+\mathcal{O}(1)$$

Then we let

$$S(n)=T(n)/n$$

Therefore,

$$S(1)=\mathcal{O}(1) \\ S(n)=S(n/2)+\mathcal{O}(1) \\ =S(n/4)+\mathcal{O}(2) \\ =S(n/2^{k})+\mathcal{O}(k) \\ =\mathcal{O}(logn) \\ T(n)=n\cdot S(n)=\mathcal{O}(n\cdot logn)$$