冒泡/合并排序算法类型：需要校正证明

Question

得到了这个算法，它是冒泡排序的一个变种。如何证明它的正确性？最好通过强烈的诱导。感谢任何指点！你知道吗

Answer 1

假设some_sort(A)的时间复杂度为T(n)。你知道吗

some_sort(Array a, a + mid)

时间复杂度：T（n/2）

some_sort(Array, b-mid, b)

时间复杂度：T（n/2）

some_sort(Array, a + (mid+1)//2, b - (mid+1)//2)

时间复杂度：T（n/2）

---

for i in range(n):
    some_sort(Array a, a + mid)                      # Will be called n times.
    some_sort(Array, b-mid, b)                       # Will be called n times.
    some_sort(Array, a + (mid+1)//2, b - (mid+1)//2) # Will be called n times.

T(n) = n * T(n / 2) + n * T(n / 2) + n * T(n / 2) + O(1)
T(n) = 3 * n * T(n / 2) + O(1)

利用马斯特斯定理我们得到：

T(n) = n^log2(3 * n)