import random


def insertion(data):
    for i in range(len(data)):
        j = i - 1
        key = data[i]
        while data[j] > key and j >= 0:
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = key
    return data

def quickSort(alist):
   quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
   if first<last:

       splitpoint = partition(alist,first,last)

       quickSortHelper(alist,first,splitpoint-1)
       quickSortHelper(alist,splitpoint+1,last)


def partition(alist, first, last):
   pivotvalue = alist[first]

   leftmark = first+1
   rightmark = last

   done = False
   while not done:

       while leftmark <= rightmark and \
               alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while alist[rightmark] >= pivotvalue and \
               rightmark >= leftmark:
           rightmark = rightmark -1

       if rightmark < leftmark:
           done = True
       else:
           alist[leftmark], alist[rightmark] = alist[rightmark], alist[leftmark]

   alist[first], alist[rightmark] = alist[rightmark], alist[first]



   return rightmark


def bubbleSort(a):
    n = len(a)
    for i in range(n-1):
        f = 0
        for j in range(n-i-1):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
                f = 1
        if f == 0:
            break
    return a

def ShakeSort(a):
    left = 0
    right = len(a) - 1
    while left <= right:
        for i in range(left,right):
            if a[i] > a[i + 1]:
                a[i], a[i +1] = a[i+1], a[i]
        right -= 1

        for i in range(right,left,-1):
            if a[i] < a[i - 1]:
                a[i], a[i-1] = a[i-1],a[i]
        left += 1

    return a

def gcd (a, b):
    return abs(a) if b == 0 else gcd(b, a % b)

def qsort(L):
    if L: return qsort([x for x in L if x < L[0]]) + [x for x in L if x == L[0]] + qsort([x for x in L if x > L[0]])
    return []

def insertion_sort_m(a):
    for i in range(len(a)):
        tmp = a[i]
        j = i - 1
        while j >= 0 and tmp < a[j]:
            a[j+1], a[j] = a[j], a[j+1]
            j -= 1
    return(a)


a = [random.randint(0, 100) for i in range(10)]
#a = [3, 2, 7 ,5]
#a = [54,26,93,17,77,31,44,55,20]
#print(a)
#insertion(a)
#quickSort(a)
#bubbleSort(a)
#ShakeSort(a)
print(insertion_sort_m(a))