# Author: OMKAR PATHAK
# Created On: 31st July 2017

#  Best = Average = O(nlog(n)), Worst = O(n ^ 2)

# quick_sort algorithm
def sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return sort(left) + middle + sort(right)

# time complexities
def bestcase_complexity():
    return 'O(nlogn)'

def averagecase_complexity():
    return 'O(nlogn)'

def worstcase_complexity():
    return 'O(n ^ 2)'

# easily retrieve the source code of the sort function
def get_code():
    import inspect
    return inspect.getsource(sort)