归并排序总共分3步：
1.如果待排序的数组中只有一个元素，直接返回，否则继续往下执行
2.将数组均分成2组，然后递归调用此函数，返回值是排好的数组
3.将两个排好的数组再排序成一个数组，如果两个数组一共有n个元素，那么需要判断n-1次
设：执行一个判断语句需要消耗一个常数的时间C（例如：需要消耗3ms）
设：此函数排序一个长度为n的数组需要消耗T(n)的时间
则：T(n) = C + 2*T(n/2) + C(n-1) = 2*T(n/2) + Cn
这个怎么求解呢？
注意到：T(1) = C , 因为根据第一步，当只有一个元素的时候就直接返回了
T(n)= 2*T(n/2) + Cn
= 2*(2*T(n/(2^2)) +Cn/2 ) + Cn
= (2^2)*T(n/(2^2)) + 2Cn
= (2^2)*( 2*T(n/(2^3)) + Cn/(2^2) ) + 2Cn
= (2^3)*T(n/(2^3)) + 3Cn
......
= (2^X)*T(n/(2^X)) + XCn
想令T(n/(2^X)) = T(1)，即：n/(2^X) = 1 ; n = (2^X) ; X = lgn/lg2
所以：T(n) = n*T(1) + lgn/lg2*Cn
= Cn + lgn/lg2*Cn
= C(n*lgn/lg2 + n)
对应的复杂度为O(n*lgn/lg2),因为n是n*lgn/lg2的低阶项