In-place quicksort algorithm in Python 2

Question

I have tried to implement an in-place quicksort Algorithm in Python 2. Please suggest how I can

1. Make the code more efficient
2. Increase readability
3. Improve writing style
4. Make it more Pythonic

def swap(x,y):
    return y,x


def sort(ar, start, end, l):

    if start<end-1:

        # pivot element is taken as the last element
        p = ar[end-1]

        ind=start-1

        # when a smaller no. than pivot is found, swap it with first bigger-tahn-pivot element. 
        # keep index as the recently swapped smaller integer, if no smaller number found, than index is start-1 because pivot is out as first element

        for i in xrange(start,end-1):
            if ar[i]<p:
                ind=i
                for j in xrange(0,i):
                    if ar[j]>p:
                        ind=j
                        ar[i],ar[j] = swap(ar[i],ar[j])
                        break

        #Swap pivot with the first bigger-than-pivot number            
        ar[ind+1], ar[end-1] = swap(ar[ind+1], p)

        ar = sort(ar, start, ind+1, l)
        ar = sort(ar, ind+2, end, l)

        return ar

    else:
        return ar

Answer 1

Your swap function is pointless. It would be far more clear just to switch the order directly in the right hand side of every assignation.

Also, in the second for loop. I'm not sure you're supposed to iterate from 0. At best it should be from start. Remember, the idea of quicksort is that you only modify the part of the array that corresponds to the function, [start, end) in this case. However, with that loop, you're now making O(n^2) iterations, which can be improved like this:

p = ar[end-1]
idx_le = start
idx_gt = end-2
while idx_le <= idx_gt:
    if ar[idx_le] <= p:
        idx_le += 1
    else:
        ar[idx_gt], ar[idx_le] = ar[idx_le], ar[idx_gt]
        idx_gt -= 1

ar[idx_le], ar[end-1] = ar[end-1], ar[idx_le]
return ar

The main idea is to keep track where the elements less than p should be placed, same with the elements greater than p. The new recursion should be [start, idx_le) [idx_le+1, end).