Mysterious Sort

Chris received a mysterious function written in Python. This function takes in a list L and sort the range \([i,j]\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def sort(L, i, j):
    if L[i] > L[j]:
        L[i], L[j] = L[j], L[i]

    if j - i + 1 > 2:
        t = (j - i + 1) / 3
        sort(L, i, j - t)
        sort(L, i + t, j)
        sort(L, i, j - t)

    return L

What is the time complexity of this mysterious algorithm?

×

Problem Loading...

Note Loading...

Set Loading...