QuickSort in Python - program hangs for larger input sizes?

Question

Pretty confused about this because I've verified correct logical output for small enough testcases (N = 20). I try doing N = 10,000 numbers and the program just hangs and I don't understand why... I've implemented the algorithm as simply as I can.

Also, calling sorted(data) on my N = 10k list seems to work almost instantly. So I'm convinced my algorithm just gets stuck somewhere.

Here is the code:

def QuickSort(array):
    qsort(array, 0, len(array))


def qsort(arr, left, right):
    if ((right - left) < 2):
        return

    pivotIndex = choosePivot0(arr, left, right)

    newPivotIndex = partition(arr, pivotIndex, left, right)

    qsort(arr, 0, newPivotIndex)
    qsort(arr, newPivotIndex + 1, right)

def partition(arr, pivotIndex, left, right):
    swap(arr, pivotIndex, left)
    pivot = arr[left]
    i = left + 1
    for j in range(left+1, right):
        if (arr[j] < pivot):
            swap(arr, i, j)
            i = i + 1

    swap(arr, left, i-1) #put pivot back where it belongs
    #cobj.count = cobj.count + (right - left - 1) #add m-1 the #of comparisons
    return (i-1) #give back where the pivot resides



def swap(array, i, j):
    temp = array[i]
    array[i] = array[j]
    array[j] = temp

def choosePivot0(array, left, right):
    return randint(left, right-1) #random

So I'm pretty lost as to why this could be happening. Thanks for any help.

Answer 1

There seems to be a typo in the following line:

qsort(arr, 0, newPivotIndex)

I think it should be like this.

qsort(arr, left, newPivotIndex)

Otherwise the function will work somehow only for some of the input data sets. That is why the algorithm gets stuck.

Answer 2

Note: I haven't check your algorithm so there maybe be a problem with it / python may not like it for some reason but: Quick sort will approximately improve sorting time from N^2 to N log(N), but maybe as bad as N^2 depending on input data. With optimal data, N=10,000 compared to N=20, would be a factor of 40,000/26 = 1538 times slower. Perhaps it's just processing?

With worst case data it will be 100,000,000 / 400 = 25,000 times slower. What's your data?