N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

# 내 풀이

n = int(input())
arr = []

for x in range(n):
    arr.append(int(input()))

def mergesplit(arr):
    if len(arr) ==1:
        return arr
    medium = int(len(arr) / 2)
    left = mergesplit(arr[:medium])
    right = mergesplit(arr[medium:])
    return merge(left, right)

def merge(left, right):
    merged_list = []
    left_index, right_index = 0, 0

    while len(left) > left_index and len(right) > right_index:
        if left[left_index] < right[right_index]:
            merged_list.append(left[left_index])
            left_index+=1

        elif left[left_index] > right[right_index]:
            merged_list.append(right[right_index])
            right_index+=1

    while len(left)> left_index:
        merged_list.append(left[left_index])
        left_index += 1

    while len(right) > right_index:
        merged_list.append(right[right_index])
        right_index += 1

    return merged_list

result = mergesplit(arr)

for x in result:
    print(x)

# 다른 사람 풀이 1

def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])
    left_idx, right_idx, array_idx = 0, 0, 0

    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] < right[right_idx]:
            array[array_idx] = left[left_idx]
            left_idx+=1
        else:
            array[array_idx] = right[right_idx]
            right_idx+=1
        array_idx+=1

    if left_idx == len(left):
        while right_idx<len(right):
            array[array_idx] = right[right_idx]
            right_idx+=1
            array_idx+=1
    elif right_idx == len(right):
        while left_idx < len(left):
            array[array_idx] = left[left_idx]
            left_idx+=1
            array_idx+=1
    return array

n = int(input())
array = []

for x in range(n):
    array.append(int(input()))

array = merge_sort(array)

for x in array:
    print(x)

# 다른 사람 풀이 2

n = int(input())

data = []
for _ in range(n):
    data.append(int(input()))
data.sort()

for x in data:
    print(x)