Quicksort Algorithm

from random import randint
from timer import timed


def sort(items, low, high):
    '''
    Three-way Partition
    . quick sort can be inplace as well, in order to reduce space complexity
      using inplace sorting and have support for duplicate elements you need to
      perform a three-way partition as follows
    '''
    if low >= high:
        return items

    pivot = items[randint(low, high)]  # selecting a pivot
    # initialize variables for partition
    left = low    # [low, left) - less than elements
    right = low   # [left, right) - equal to pivot
    upper = high  # [right, upper] - unexamined, (upper, high] - greater than
    while right <= upper:
        if items[right] < pivot:
            items[left], items[right] = items[right], items[left]
            left += 1
            right += 1
        elif items[right] > pivot:
            items[right], items[upper] = items[upper], items[right]
            upper -= 1
        else:
            right += 1

    sort(items, low, left-1)
    sort(items, right, high)
    return items


@timed
def to_sort(items): sort(items, 0, len(items) - 1)


# Testing
items = [randint(1, 10) for _ in range(10)]
print(items)
print(sort(items, 0, len(items) - 1))

# Benchmarking: to test how scalable the algorithm is
to_sort([randint(1, 1000) for _ in range(1000)])
to_sort([randint(1, 1000) for _ in range(10000)])
'''
OUTPUT:
[4, 10, 5, 6, 2, 1, 7, 10, 1, 7]
[1, 1, 2, 4, 5, 6, 7, 7, 10, 10]
Finished 'to_sort' in 0.0039396000 secs
Finished 'to_sort' in 0.0343496000 secs
'''