# Quick sort
# The idea is to pick a pivot point and sort the array such that
# the left part of the coverging point is smaller than the pivor point,
# the right larger.
# converging point is found when the right pointer is smaller than the left pointer
import pytest

def test_quick_sort():
    input1 = [31, 23, 43, 56, 9]
    input2 = []
    assert quick_sort(input1) == [9, 23, 31, 43, 56]
    assert quick_sort(input2) == []

def quick_sort(input):
    qs_helper(input, 0, len(input)-1)
    return input

def qs_helper(input, start, end):
    if start < end:
        partition = qs_partition(input, start, end)
        # left partition
        qs_helper(input, start, partition-1)
        # right partition
        qs_helper(input, partition+1, end)

def qs_partition(input, start, end):
    pivot = input[start]
    left = start + 1
    right = end
    done = False
    while not done:
        while left <= right and input[left] < pivot:
            left += 1
        while input[right] > pivot and left <= right:
            right -= 1
        if left > right: done = True
        else:
            input[left], input[right] = input[right], input[left]

    input[start], input[right] = input[right], input[start]
    return right