本文章从归并排序的算法代码出发，通过一步步分析计算出此算法的时间复杂度。
关于归并排序的分析，我上一篇博客有：归并排序分析
这里只进行代码分析。
先看算法的代码：
private int[] merge_sort(int[] input,int start,int end){ if(start<end){ int mid=(start+end)/2; merge_sort(input,start,mid); merge_sort(input,mid+1,end); merge(input,start,mid,end); } return input; } private void merge(int[] input,int start,int mid,int end){ int k=start; int l=mid+1; int[] tempA=new int[end-start+1]; int m=0; //一次比较两个数组部分的首元素 while(k<=mid&&l<=end){ if(input[k]<input[l]){ tempA[m]=input[k]; k++; }else{ tempA[m]=input[l]; l++; } m++; } //剩余部分加入到末尾 while(k<=mid){ tempA[m]=input[k]; m++; k++; } //剩余部分加入到末尾 while(l<=end){ tempA[m]=input[l]; m++; l++; } //整个函数中，这个for循环最耗时，循环次数为输入规模n for(int i=start,j=0;i<=end;i++,j++){ input[i]=tempA[j]; } }分析：
假设一个归并排序的时间复杂度为T(n),归并排序的核心思想如函数merge_sort所示，把问题拆分成两个规模更小的子问题，然后再合并子问题。
假设合并子问题的函数merge时间复杂度为F(n)。则可以得到归并排序的时间复杂度计算公式为：T(n)=2T(n/2)+F(n)。
而当输入规模为1时候，T(1)=Θ（1）。所以:
T(n)=T(n/2)+T(n/2)+F(n)=2T(n/2)+F(n)
=T(n/4)+T(n/4)+F(n/2)+T(n/4)+T(n/4)+F(n/2)+F(n)=4T(n/4)+2F(n/2)+F(n)=4T(n/4)+2F(n)
=T(n/8)+T(n/8)+F(n/4)+T(n/8)+T(n/8)+F(n/4)+F(n/2)+T(n/8)+T(n/8)+F(n/4)+T(n/8)+T(n/8)+F(n/4)+F(n/2)+F(n)=8T(n/8)+3F(n)
=16T(n/16)+4F(n)
.......
=nT(1)+Log₂nF(n)
=nΘ（1）+Log₂nF(n)=Θ（n）+Log₂nF(n)
式子中F（n）即是合并数组函数merge的时间复杂度，根据代码进行分析，函数中时间复杂度最高的语句是最后的for循环，执行了n次循环，而其他语句都是小于n的常数级的时间复杂度，所以F(n)=n+c₁+c₂+.....式子中的c代表式中除去for循环各个语句的执行次数，低数量级的复杂度被忽略，因此F(n)=Θ(n)。
综上所述，归并排序的时间复杂度T(n)=Θ（n）+Log₂nΘ（n）复杂度。
低数量级的复杂度被忽略，因此：T(n)=ΘLog₂nΘ（n）。
