수 정렬하기 2(# 2751) 파이썬

문제설명

1 <= N <= 1,000,000  이라는 조건 때문에 시간복잡도가 O(NlogN) 이하여야 합니다. 

마찬가지로 내장된 정렬(sort)을 사용하여 풀 수 있습니다. 단, 시간복잡도가 NlogN인 알고리즘은 병합 정렬, 힙 정렬 등이 있는데, 그 중 병합 정렬을 사용한 풀이를 보여드리겠습니다. 

 

수 정렬하기2(# 2751) 파이썬 코드

import sys

def mergeSort(arr):  # (NlogN), stable
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2
    left = mergeSort(arr[:mid])
    right = mergeSort(arr[mid:])

    merged_arr = []
    l = r = 0
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            merged_arr.append(left[l])
            l += 1
        else:
            merged_arr.append(right[r])
            r += 1
    merged_arr += left[l:]
    merged_arr += right[r:]
    return merged_arr
    
    
n = int(sys.stdin.readline())
arr = []
for i in range(n):
    arr.append(int(sys.stdin.readline()))

for i in mergeSort(arr):
    print(i)