''' Quick Sort Algorithm

    this algorithm orders an unordered list of elements by picking a pivot
    element within the list and compare each and every element within the
    list to break the original list into 2 lists, larger than pivot and
    less than pivot, this runs recursively until the smallest list is 1
    then every list is combined to form the ordered list

    #####################################################################
    the trick of this quick sort algorithm is cleverly picking the pivot,
    worst case is when extreams are selected as the pivot'''


def quick_sort(sequence):
    # length here returns the length of our data sequence
    length = len(sequence)
    # if the lenght of list is of a single element just return the element
    if length <= 1:
        return sequence

    else:
        # we label one of the element in the list "pivot" in order to compare
        # other elements to this pivot element to position accordingly
        pivot = sequence.pop()

    # here we define 2 lists, one list contains elements less than pivot from
    # our original sequence, other list contain elements greater than pivot
    items_greater = []
    items_lower = []

    for item in sequence:  # passing through our sequence
        if item > pivot:   # compare each elements in our sequence with pivot
            # add element to items_greater if larger than pivot
            items_greater.append(item)

        else:
            # add element to items_lower if smaller or equal than pivot
            items_lower.append(item)
    # pass sequence recursively until length is 1 and combine every list
    return quick_sort(items_lower) + [pivot] + quick_sort(items_greater)