"""

Quick Sort

Quick sort selects a pivot element, partitions the array around the

pivot, and recursively sorts the two partitions.

Reference: https://en.wikipedia.org/wiki/Quicksort

Complexity:

Time: O(n log n) best / O(n log n) average / O(n^2) worst

Space: O(log n)

"""

from __future__ import annotations

def quick_sort(array: list[int]) -> list[int]:

"""Sort an array in ascending order using quick sort.

Args:

array: List of integers to sort.

Returns:

A sorted list.

Examples:

>>> quick_sort([3, 1, 2])

[1, 2, 3]

"""

_quick_sort_recursive(array, 0, len(array) - 1)

return array

def _quick_sort_recursive(array: list[int], first: int, last: int) -> None:

"""Recursively sort *array[first..last]* in-place."""

if first < last:

pivot = _partition(array, first, last)

_quick_sort_recursive(array, first, pivot - 1)

_quick_sort_recursive(array, pivot + 1, last)

def _partition(array: list[int], first: int, last: int) -> int:

"""Partition *array[first..last]* using the last element as pivot.

Returns:

The final index of the pivot element.

"""

wall = first

for pos in range(first, last):

if array[pos] < array[last]:

array[pos], array[wall] = array[wall], array[pos]

wall += 1

array[wall], array[last] = array[last], array[wall]

return wall