为什么排序算法可以正常工作？

Question

我得到了一个排序算法。我知道它可以用许多其他更简单的方式编写，但这不是我问题的重点。

这是算法:

sort(A : Array of N, i : N, j : N)
assert j-i+1 isTwoPotency
if A[i] > A[j] then swap A[i] and A[j]
if i+1 < j then
    k:= (j − i + 1)/4
    sort(A, i, j − 2k)
    sort(A, j − 2k + 1, j)
    sort(A, i + k, j − k)
    sort(A, i, j − 2k)
    sort(A, j − 2k + 1, j)
    sort(A, i + k, j − k)

我的问题是，为什么算法在以下情况下可以正常工作？

sort(A, 1, length(A))

数组将是：

A[1 . . . length(A)]

length(A) 是两个效能，我们可以假设 没有相同的数字数组。我已经对其进行了测试，没有出现任何错误，因此我认为它可以正常工作。但是我如何证明该算法在这些条件下始终正确运行？

而且我想知道算法需要多长时间运行时间。如果你能给我运行时间作为大 theta 符号（这是我最理解的）

就太好了

f(n) = Θ(g(n))

Answer 1

正确性

将数组分为四个部分，A1 到 A4，并考虑每个元素最终应该位于的子数组。

经过前两次递归调用，所有属于A1的元素都位于A1或A3中。同样所有A4元素都位于A2或A4.
第三次递归调用后，所有A1元素都在A1或A2中，所有A4元素都在A3或A4中
在接下来的两次递归调用后，A1中的所有元素有序排列在A1中，A4中的元素有序排列在A4中。这会将所有 A2 和 A3 元素留在 A2 或 A3 中。
在最后一次递归调用之后，所有 A2 和 A3 元素都按排序顺序位于正确的子数组中。这样数组就排序好了。

插图：

运行时间

注意，当我们对长度为n的数组执行算法时，我们必须对长度为n/2的数组执行六次算法。这会产生以下重复：

T(1) = O(1).
T(n) = 6 T(n/2) + O(1).

求解递归我们得到T(n) = O(6^log2(n)) = O(n^log2(6)) ≈ O(n^2.585)

为什么排序算法可以正常工作？

Why does the sorting algorithm work correctly?

sorting

algorithm

performance

big-o

正确性

运行时间