什么是归并排序？
归并排序的概念十分简单，就是“分而治之”的思想。这里我直接从网上找了一份对归并排序算法的比较好的介绍排序算法
。
计算时间复杂度
关键是怎么计算时间复杂度？
我们在假设数组的长度为n的基础上进行归并排序，假设排序的总共用时为
T
[
n
]
T[n]
T[n]，则：
第一次，将数组对半分，分别对两个子数组进行排序，并合并两个有序数组，所需要的时间为
T
[
n
]
=
T
[
⌈
n
−
1
2
⌉
]
+
T
[
⌊
n
+
1
2
⌋
]
+
Θ
[
n
]
T[n]=T[\lceil\frac{n-1}{2}\rceil]+T[\lfloor\frac{n+1}{2}\rfloor]+\Theta[n]
T[n]=T[⌈2n−1⌉]+T[⌊2n+1⌋]+Θ[n]
我们将其简写为
T
[
n
]
=
2
⋅
T
[
n
2
]
+
Θ
[
n
]
T[n]=2\cdot{T[\frac{n}{2}]}+\Theta[n]
T[n]=2⋅T[2n]+Θ[n]
同理，第二次，继续将子数组对半分，并分别对两个子子数组进行排序，并合并两个有序数组，所需要的时间为
T
[
n
2
]
=
2
⋅
T
[
n
4
]
+
Θ
[
n
2
]
T[\frac{n}{2}]=2\cdot{T[\frac{n}{4}]}+\Theta[\frac{n}{2}]
T[2n]=2⋅T[4n]+Θ[2n]
依照这个规律，我们计算
T
[
n
]
、
T
[
n
2
]
、
T
[
n
4
]
。
。
。
、
T
[
2
]
、
T
[
1
]
T[n]、T[\frac{n}{2}]、T[\frac{n}{4}]。。。、T[2]、T[1]
T[n]、T[2n]、T[4n]。。。、T[2]、T[1]，且最终可得到下面这个式子：
T
[
n
]
=
Θ
[
n
]
+
2
Θ
[
n
2
]
+
4
Θ
[
n
4
]
+
.
.
.
+
n
Θ
[
1
]
T
[
n
]
=
n
+
2
⋅
n
2
+
4
⋅
n
4
+
.
.
.
+
n
⋅
1
T[n]=\Theta[n]+2\Theta[\frac{n}{2}]+4\Theta[\frac{n}{4}]+...+n\Theta[1] T[n]=n+2\cdot\frac{n}{2}+4\cdot\frac{n}{4}+...+n\cdot1
T[n]=Θ[n]+2Θ[2n]+4Θ[4n]+...+nΘ[1]T[n]=n+2⋅2n+4⋅4n+...+n⋅1
我们可以把
Θ
[
n
]
\Theta[n]
Θ[n]理解为在
n
n
n时间内完成的程序，则
T
[
n
]
=
n
+
2
⋅
n
2
+
4
⋅
n
4
+
.
.
.
+
n
⋅
1
=
n
+
n
+
n
+
.
.
.
+
n
=
n
⋅
l
o
g
2
n
\begin{aligned} T[n]&=n+2\cdot\frac{n}{2}+4\cdot\frac{n}{4}+...+n\cdot1 \\&=n+n+n+...+n \\&=n\cdot{log_2{n}} \end{aligned}
T[n]=n+2⋅2n+4⋅4n+...+n⋅1=n+n+n+...+n=n⋅log2n
这里，
l
o
g
2
n
log_2{n}
log2n是怎么冒出来的？就是因为一共有
l
o
g
2
n
log_2{n}
log2n个
n
n
n相乘（不懂的话，自己好好思考一下）。
因此，最终就可得到归并排序算法的时间复杂度为
n
⋅
l
o
g
2
n
n\cdot{log_2{n}}
n⋅log2n。
