Quick sort in Python

Quick sort best and the avarage runining time is \(O(n\log{}n)\).

To learn more about Python generators, see python fun.

For example to sort the above array:

def qs(a):
    if len(a) <2: #base case
        return a
    else: # recursive case
         p =  a[0] #pivot as first element of the array
         l = [e for e in a[1:] if e <= p]
         r = [e for e in a[1:] if e > p]
         return qs(l)+[p]+qs(r)

#Test         
print (qs([5,9,4,7,6,8,2,1,3]))

Quick sort complexcity

The complexcity of the quick sort can be worst as \(O(n^2)\) base on the pivotal you choose. For example, even for the sorted array if the pivotal is first element, the deapth is \(n\).