implementing quicksort and getting a bug I don't understand

Question

I have 2 functions, a function that partitions an array and quicksort itself:

def partition(a, i, j):
    h = i+1

    for k in range(i+1, j):
        if a[k] < a[i]:
            a[h],a[k] = a[k],a[h]
            h += 1
    a[i],a[h-1] = a[h-1],a[i]

    return h 

# a is an array. After function call a[i..j-1] is sorted in increasing order
def quicksort(a, i, j):
    if j-i <= 1: return

    swap(a, i, j)
    p = partition(a, i, j)

    quicksort(a, i, p)
    quicksort(a, p, j)

This works for all the test cases I tried, that is I call quicksort(a, 0, len(a)) and the list a is sorted after.

I'm trying to change the pivot element. I want to use the last element of the array as the pivot instead of the first one (like in the implementation above). For that purpose I add the following line of code to the quicksort function just before the partition:

a[i],a[j-1] = a[j-1],a[i]

and everything breaks. The maximum recursion depth gets exceeded. I don't understand why it's happening and it's driving me crazy.

Answer 1

Given input [1,2,3], it would drop into infinite loop with consistent p; switch p with p-1/p+1:

def quicksort(a, i, j):
    if j <= i: return

    swap(a, i, j)
    p = partition(a, i, j)

    quicksort(a, i, p-1)
    quicksort(a, p+1, j)