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

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)]

长度(A)是双效力,我们可以假定,有阵列内不相同的数字.我已经测试过,没有错误,所以我认为它可以正常工作.但是,如何证明算法在这些条件下始终能够正常工作？

我想知道算法需要多长时间作为运行时间.如果你能把我的运行时间作为一个重要的符号(那是我最了解的那个),那就太棒了

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)