import timeit
import random
 
 
def quick(lst):
    if not lst:
        return []
    else:
        first, rest = lst[0], lst[1:]
        great = []
        less = []
        for item in rest:
            great.append(item) if item >= first else less.append(item)
        return quick(less) + [first] + quick(great)
 
def sort(lst):
    lst.sort()
    return lst
 
 
x = [random.randint(1, 10000) for i in xrange(1, 1000)]
 
quick_t = timeit.Timer("'quick(x)'")
 
print quick_t.repeat(3, 2000)
 
sort_t = timeit.Timer("'sort(x)'")
 
print sort_t.repeat(3, 2000)

aW1wb3J0IHRpbWVpdAppbXBvcnQgcmFuZG9tCgoKZGVmIHF1aWNrKGxzdCk6CiAgICBpZiBub3QgbHN0OgogICAgICAgIHJldHVybiBbXQogICAgZWxzZToKICAgICAgICBmaXJzdCwgcmVzdCA9IGxzdFswXSwgbHN0WzE6XQogICAgICAgIGdyZWF0ID0gW10KICAgICAgICBsZXNzID0gW10KICAgICAgICBmb3IgaXRlbSBpbiByZXN0OgogICAgICAgICAgICBncmVhdC5hcHBlbmQoaXRlbSkgaWYgaXRlbSA+PSBmaXJzdCBlbHNlIGxlc3MuYXBwZW5kKGl0ZW0pCiAgICAgICAgcmV0dXJuIHF1aWNrKGxlc3MpICsgW2ZpcnN0XSArIHF1aWNrKGdyZWF0KQoKZGVmIHNvcnQobHN0KToKICAgIGxzdC5zb3J0KCkKICAgIHJldHVybiBsc3QKCgp4ID0gW3JhbmRvbS5yYW5kaW50KDEsIDEwMDAwKSBmb3IgaSBpbiB4cmFuZ2UoMSwgMTAwMCldCgpxdWlja190ID0gdGltZWl0LlRpbWVyKCIncXVpY2soeCknIikKCnByaW50IHF1aWNrX3QucmVwZWF0KDMsIDIwMDApCgpzb3J0X3QgPSB0aW1laXQuVGltZXIoIidzb3J0KHgpJyIpCgpwcmludCBzb3J0X3QucmVwZWF0KDMsIDIwMDAp