합병정렬 구현하기

문제

n개의 정수가 주어질 때, 이를 합병정렬을 이용하여 오름차순으로 정렬하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 두번째 줄에 n개의 정수가 주어진다.  

출력

첫 번째 줄에 n개의 숫자를 합병정렬을 이용하여 오름차순으로 정렬한 결과를 출력한다.

 

예제 입력

10 2 5 3 4 8 7 -1 9 10 2

예제 출력

-1 2 2 3 4 5 7 8 9 10

 

#코드

import sys
 
def merge(alist):
 
    if len(alist) > 1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]
 
        merge(lefthalf)
        merge(righthalf)
        
        i,j,k = 0,0,0
 
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] <righthalf[j]:
                alist[k] = lefthalf[i]
                i+=1
            else:
                alist[k] = righthalf[j]
                j+=1
            k+=1
        
        while i < len(lefthalf) :
            alist[k] = lefthalf[i]
            i+=1
            k+=1
 
        while j < len(righthalf) : 
            alist[k] = righthalf[j]
            j+=1
            k+=1
if __name__ == "__main__" :
  input = sys.stdin.readline
  n = int(input())
  data = list(map(int,input().split()))
      
  merge(data)
  for i in data:
    print(i, end=' ')