为什么不使用二进制插入进行插入排序被认为是最好的？
Merge sort : T(n) = n + 2*T(n/2) = O(n*log(n))
But insertion sort with binary insert : T(n) = log(n-1) + T(n-1) = O(log(n!))
and n^n > n! ; so n*log(n) > log(n!)
对于更大的 n，它确实有助于提高性能。
还是我错过了什么？
如果我问的问题太琐碎，请原谅我，我是编程新手，我只想弄清事实。
我认为您对插入排序复杂性的估计是错误的。您没有描述如何获得结果的详细信息，但您似乎忘记了插入所需的时间 - 我的意思是您需要移动排序数组的某些部分以为您插入的元素腾出位置的时间。
对 n-1 个元素进行排序后，您需要 O(log(n)) 时间来找到第 n 个元素的位置，并且需要 O(n)（悲观地）时间来移动已排序数组的一部分并为 n-元素。所以总复杂度是
O(1 + ... + n + log 1 + ... + log n) = O(n^2 + n log n) = O(n^2)。
您不会通过二进制搜索来改进您的算法，因为无论如何您都必须移动数组的一部分（以 n 为线性大小）。