[FIXED] python time complexity quick sort algorithm

Issue

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 wrote "maybe" quick sort 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).

Solution

Your sorting function isn't O(nlogn). In the worst case, you are making O(n) recursive calls.

As a simple test:

def test(n):
    nums = list(reversed(range(n)))
    return sum(quicksort(nums,0,n-1))

Then, for example, test(1100) triggers:

RecursionError: maximum recursion depth exceeded in comparison

Which wouldn't happen if you were calling partition just log(n) times.

On the other hand,

import random

def test2(n):
    nums = list(range(n))
    random.shuffle(nums)
    return sum(quicksort(nums,0,n-1))

works well even for calls like test2(100000), so you do have average case O(nlogn) complexity. This is easy to confirm numerically but difficult to prove. See https://en.wikipedia.org/wiki/Quicksort for a proof.

Answered By - John Coleman