def quick_sort_out_of_place(array):
    """Recursive QuickSort Implementation:
    - O(nlog(n)) time
    - O(n) space (out of place)
    - unstable
    - pivot = mean of the range (best on normal, numerical distributions)
    """
    # Base Case
    if len(array) < 2:
        return array
    # Recurisive Case - choose a pivot
    pivot = (min(array) + max(array)) // 2
    # Divide and Conquer - partition by the pivot
    lower_partition = [val for val in array if val < pivot]
    middle = [val for val in array if val == pivot]
    upper_partition = [val for val in array if val > pivot]
    # combine - recurse on left and right partitions
    return (
        quick_sort_out_of_place(lower_partition)
        + middle
        + quick_sort_out_of_place(upper_partition)
    )