import random
import time

a = range(10000)
random.shuffle(a)

def swap(a, m, n):
    a[m], a[n] = a[n], a[m]

def straightsort(a, s, t):
    for i in range(s, t):
        for j in range(t, i, -1):
            if a[i] > a[j]:
                swap(a, i, j)

def quicksort(a, s, t):
    if t - s <= 2:
        straightsort(a, s, t)
    else:
        k = s + (t - s)/2 + 1
        i = s
        j = t
        while i < j:
            while a[i] < k:
                i += 1
            while a[j] > k:
                j -= 1
            if i < j:
                swap(a, i, j)
        quicksort(a, s, i)
        quicksort(a, i+1, t)

ts = time.time()
print 'start:', ts
quicksort(a, 0, len(a)-1)
te = time.time()
print 'end:', te
print 'time:', te-ts