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

#  Best O(n); Average O(n^2); Worst O(n^2)

# insertion sort algorithm
def sort(List):
    for i in range(1, len(List)):
        currentNumber = List[i]
        for j in range(i - 1, -1, -1):
            if List[j] > currentNumber :
                List[j], List[j + 1] = List[j + 1], List[j]
            else:
                List[j + 1] = currentNumber
                break
    return List

# time complexities
def time_complexities():
    return '''Best Case: O(n), Average Case: O(n ^ 2), Worst Case: O(n ^ 2)'''

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