Quicksort() using python

One method of sorting lists is to use the quicksort.  The elements in the list must have a strict weak order and the index of the array can be of any discrete type.


Follow these steps to implement:

1. Choose any element of the list to be the pivot.
2. Divide all other elements (except the pivot) into two partitions.
   • All elements less than the pivot must be in the first partition (lower half list).
   • All elements greater than the pivot must be in the second partition (upper half list).
3. Use recursion to sort both partitions.
4. Join the first sorted partition, the pivot, and the second sorted partition

The run time of quicksort ranges from O(n log n) with the best pivots, to O(n²) with the worst pivots, where n is the number of elements in the list.  (O is complexity)

def qsort(list):
    if not list:
        return []
    else:
        pivot = list[0]
        less = [x for x in list     if x <  pivot]
        more = [x for x in list[1:] if x >= pivot]
        return qsort(less) + [pivot] + qsort(more)

Example:
someList = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3]
print qsort( someList )
[1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9, 9, 9]


Enjoy the sort.