quick_sort_v2.py

#---------------------------------------------------------------
# QUICK SORT V2
#---------------------------------------------------------------

# https://leetcode.com/explore/learn/card/recursion-ii/470/divide-and-conquer/2870/
# https://rust-algo.club/sorting/quicksort/index.html

"""

Time complexity

    Best : O(N Log N)
    Avg : O(N Log N)
    Worst : O(N Log N)`


Space complexity

    O(N)

"""

def quicksort(lst):
    """
    Sorts an array in the ascending order in O(n log n) time
    :param nums: a list of numbers
    :return: the sorted list
    """
    n = len(lst)
    qsort(lst, 0, n - 1)

def qsort(lst, lo, hi):
    """
    Helper
    :param lst: the list to sort
    :param lo:  the index of the first element in the list
    :param hi:  the index of the last element in the list
    :return: the sorted list
    """
    if lo < hi:
        p = partition(lst, lo, hi)
        qsort(lst, lo, p - 1)
        qsort(lst, p + 1, hi)

def partition(lst, lo, hi):
    """
    Picks the last element hi as a pivot
     and returns the index of pivot value in the sorted array
    """
    pivot = lst[hi]
    i = lo
    for j in range(lo, hi):
        if lst[j] < pivot:
            lst[i], lst[j] = lst[j], lst[i]
            i += 1
    lst[i], lst[hi] = lst[hi], lst[i]
    return i