sorting - 梳状排序的计算复杂度

Question

使用这个伪代码，请帮助我计算梳状排序在最坏情况、最佳情况和平均情况下的复杂度。知道在最坏的情况下，它的复杂度是 O(n^2)，在平均情况下，它的复杂度是 O(n^2/2^p)，其中 p 是一个递增的数字，在最好的情况下，它的复杂度是O(n.logn)

    gap := input.size  
sorted := false
loop while sorted = false
    gap := floor(gap / 1.3)
    if gap ≤ 1 then
        gap := 1
        sorted := true 
    end if
    i := 0
    loop for i to input.size - gap  
        if input[i] > input[i+gap] then
            swap(input[i], input[i+gap])
            sorted := false 
         end if
         i := i + 1
     end loop