Quick Sort

# Best and average case scenario is nlogn
# worst case scenario is O(n**2)

def quick_sort(sequence):
    
    if len(sequence) <= 1: # return sequence if it 1 or less than 1
        return sequence

    lower = []
    higher = []

    pivot = sequence.pop() # select the last element as pivot. We can select any element we want.

    # create two arrays which are less than and equal to or higher than pivot
    for item in sequence:
        if item < pivot:
            lower.append(item) 

        else:
            higher.append(item)
    
    # use recursion on each lower and higher array for sorting
    # concatenante the results
    return quick_sort(lower) + [pivot] + quick_sort(higher)   

# Check if the function is working correctly
quick_sort([5,8,3,9,5,0,9,387,9486,9,4,56])

[0, 3, 4, 5, 5, 8, 9, 9, 9, 56, 387, 9486]