from functions import *
import sys

N, algName = int(sys.argv[1]), sys.argv[2]
arr = read(N)
result = list()
if algName.lower() == "bubblesort":
    result = bubbleSort(arr)
elif algName.lower() == "mergesort":
    result = mergeSort(arr, 0, int(N) - 1)
elif algName.lower() == "insertionsort":
    result = insertionSort(arr)
write(result)


def insertionSort(arr):

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

def mergeSort(A, p, r):

    def merge(A, p, q, r):
        n = q - p + 1
        m = r - q
        L = [0] * n
        R = [0] * m

        for i in range(n):
            L[i] = A[p + i]

        for j in range(m):
            R[j] = A[q + j + 1]

        i, j = 0, 0
        k = p

        while i < n and j < m:

            if L[i] <= R[j]:
                A[k] = L[i]
                i = i + 1

            else:
                A[k] = R[j]
                j = j + 1
            k += 1

        while i < n:
            A[k] = L[i]
            i += 1
            k += 1

        while j < m:
            A[k] = R[j]
            j += 1
            k += 1

    if p < r:
        q = (p + r) // 2
        mergeSort(A, p, q)
        mergeSort(A, q + 1, r)
        merge(A, p, q, r)
    return A

def bubbleSort(arr):

    for j in range(len(arr)):
        i = 0
        while i < len(arr) - 1 - j:

            if arr[i] > arr[i + 1]:
                arr[i] , arr[i + 1] = arr[i + 1], arr[i]
                i += 1
            else:
                i += 1
    return arr

def read(N):
    arr = list()
    f = open("data.txt", "r")
    for i in range(N):
        context = f.readline()
        arr.append(int(context.strip("\n")))
    return arr

def write(arr):
    f = open("sorted.txt", "w")
    for i in arr:
        f.write(str(i) + "\n")