Some sorts

qsort.py

import random
import sys
import time

# sys.setrecursionlimit(10000)

def qsort(a):
    if len(a) <= 1: return a
    pivot = random.choice(a)
    left = qsort([x for x in a if x < pivot])
    right = qsort([x for x in a if x > pivot])
    return left + [x for x in a if x == pivot] + right

def qsort_double_pointers(a):
    def partition(l, r):
        lo = l
        pivot = a[lo]
        l += 1
        while True:
            while l < r and a[l] < pivot: l += 1
            while l <= r and a[r] >= pivot: r -= 1
            if l >= r: break
            a[l], a[r] = a[r], a[l]
        a[lo], a[r] = a[r], a[lo]
        return r

    def qsort(l, r):
        if l >= r: return
        pivot_idx = random.randint(l, r)
        pivot = a[pivot_idx]
        mid = partition(l, r)
        qsort(l, mid - 1)
        qsort(mid + 1, r)

    qsort(0, len(a)-1)

def check(a):
    for i in range(1, len(a)):
        assert a[i] >= a[i-1]

if __name__ == '__main__':
    for _ in range(100):
        l = random.randint(5, 1000000)
        a = [random.randint(-20000000, 20000000) for _ in range(l)]
        print(l)
        start = time.perf_counter()
        b = qsort(a)
        end = time.perf_counter()
        print(end - start)
        check(b)
        start = time.perf_counter()
        qsort_double_pointers(a)
        end = time.perf_counter()
        print(end - start)
        check(a)