quick sort

qsort.py

import random
import timeit
import itertools

def is_sorted(a):
    return all(a[i] <= a[i+1] for i in xrange(len(a)-1))

def qsort(a):
    def impl(a, left, right):
        if left >= right:
            return
        pivot = a[(left + right) / 2]
        i = left
        j = right
        while True:
            while pivot > a[i]:
                i = i + 1
            while pivot < a[j]:
                j = j - 1
            if i < j:
                a[i], a[j] = a[j], a[i]
                i = i + 1
                j = j - 1
            else:
                break
        impl(a, left, i - 1)
        impl(a, j + 1, right)
    left = 0
    right = len(a) - 1
    impl(a, left, right)

def test1():
    a = range(100000)
    random.shuffle(a)
    a.sort()
    assert is_sorted(a)

def test2():
    a = range(100000)
    random.shuffle(a)
    qsort(a)
    assert is_sorted(a)

if __name__ == '__main__':
    print timeit.Timer('test1()', setup='from __main__ import test1').timeit(10)
    print timeit.Timer('test2()', setup='from __main__ import test2').timeit(10)