[백준][Python] 2751번 수 정렬하기2 - MergeSort

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

 

 

Python

import sys
input = sys.stdin.readline

n = int(input())
arr = [int(input()) for _ in range(n)]


def merge(low, mid, high):
    i, j = low, mid+1
    sort = []
    while i <= mid and j <= high:
        if arr[i] == arr[j]:
            sort.append(arr[i])
            sort.append(arr[j])
            i, j = i+1, j+1
        elif arr[i] < arr[j]:
            sort.append(arr[i])
            i += 1
        elif arr[i] > arr[j]:
            sort.append(arr[j])
            j += 1

    while i <= mid:
        sort.append(arr[i])
        i += 1
    while j <= high:
        sort.append(arr[j])
        j += 1

    arr[low:high+1] = sort


def mergeSort(low, high):
    if low < high:
        mid = (low+high) // 2
        mergeSort(low, mid)
        mergeSort(mid+1, high)
        return merge(low, mid, high)


mergeSort(0, n-1)
for a in arr:
    print(a)