2751. 수 정렬하기 2

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

시간복잡도 O(nlogn)인 알고리즘으로 풀어보세요.

 

합병정렬

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

합병 정렬 - 위키백과, 우리 모두의 백과사전

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
        
    mid = len(arr)//2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    
    merged_arr = []
    i, j = 0, 0
    
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] <= right_arr[j]:
            merged_arr.append(left_arr[i])
            i += 1
        else:
            merged_arr.append(right_arr[j])
            j += 1
            
    merged_arr = merged_arr + left_arr[i:] + right_arr[j:]
    return merged_arr
    
N = int(input())
numbers = [int(input()) for _ in range(N)]
sorted_numbers = merge_sort(numbers)

for number in sorted_numbers:
    print(number)

 

 

• 백준 알고리즘 사이트에서는 시간초과 문제로 인해 PyPy3파일로 제출해야 합니다.