quicksort

import random

def quicksort(arr):
    if arr is None:
        return arr

    return _quicksort(arr, 0, len(arr))


def _quicksort(arr, start, end):
    if start + 1 >= end:
        return arr

    pivot = _partition(arr, start, end)
    _quicksort(arr, start, pivot)
    _quicksort(arr, pivot + 1, end)

    return arr


def _partition(arr, start, end):
    pivot = start
    l = start
    r = start + 1
    while r < end:
        if arr[r] <= arr[pivot]:
            l = l + 1
            tmp = arr[l]
            arr[l] = arr[r]
            arr[r] = tmp
        r = r + 1

    tmp = arr[l]
    arr[l] = arr[pivot]
    arr[pivot] = tmp

    return l


print quicksort(None)
print quicksort([])
print quicksort([3])
print quicksort([3,1])
print quicksort([3,1,2])
print quicksort([int(random.random() * 200) for x in range(1, 200)])