python time complexity quick sort algorithm

Question

def partition(A, l, r):
    p = A[l]
    stack = A[l]
    A[l] = A[r]
    A[r] = stack
    s = l

    for i in range(l, r):

        if A[i] <= p:

            stack2 = A[i]
            A[i] = A[s]
            A[s] = stack2
            s += 1

    stack3 = A[s]
    A[s] = A[r]
    A[r] = stack3

    return s

def quicksort(A, l, r):

    if l < r:

        q = partition(A, l, r)
        quicksort(A, l, q - 1)
        quicksort(A, q + 1, r)
    return A

I've written "maybe" quicksort algorithm, as I've noticed here the time complexity of partition was O(n) because of the for loop, Also the complexity in quicksort seems to be at least O(n). The question: how is it possible for the entire code to have total time complexity of O(nlogn).

Answer 1

You partition by 2 each level till you get individual elements. Partitioning and comparison what makes the time complexity. You make n comparisons in each level and you will be partioning log2(n) times.

In the worst case, your array is already sorted and you will be partitioning n times and still make n comparisons in each level.