Question

归并排序的时间复杂度O(n*log n)是怎么得来的，求大神详细的讲解一下

Answer 1

首先你说归并排序最坏的情形为O(NlogN)，这是不正确的归并排序如果不借助辅助空间的话，复杂度为O(n^2)，借助的话就是O(nlogn)(O(nlog2n))归并排序 平均复杂度是 O(nlogn) 比较快
快速排序快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。”
随机化快速排序的唯一缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直接减弱。对于极限情况，即对于n个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。解决方法是用一种方法进行扫描，使没有交换的情况下主元保留在原位置。
综合来说快速排序速度最快，时间复杂度最小。希望对你有所帮助！

追问

我问的是归并排序

Answer 2

首先，你要理解两个长度为n/2的的数组做归并，这个时间复杂度是O(n)。
然后，因为归并排序要不断的把原来数组分成两份，这个递归的过程是O(logn)。比如说你想要排序的数组长度为8，然后不断一的一分为二，就是8——>4——>2——>1。一共拆了3次，2^3 = 8，或者3是以二为底的8的对数。log就是这样来的。
然后两个再相乘，时间复杂度了就是O(nlogn)了。