병합 정렬 in python

고급 정렬 중 병합정렬에 대해 공부해보자.

 

병합정렬은 모든 리스트의 요소를 한개의 배열로 쪼개고 하나씩 위로 올리면서 정렬을 하는 방식이다.

그래서 리스트의 모든 요소가 한개의 배열로 쪼개질 때, log(n)이고 각 요소를 정렬할 때 n의 복잡도가 들면서 최종적으로 O(nlog(N))의 복잡도가 든다.

 

log(n)은 만약 8개의 요소가 있으면 각각을 한개로 쪼개는데 3번 분류된다. 2^3.

2의 몇승으로 늘어나기 때문에 log를 붙인다.

 

이걸 코드로 짜면

#병합정렬

def merge_sort(array):
  if len(array)<=1:
    return array
    
  mid=len(array)//2
  left=merge_sort(array[:mid])
  right=merge_sort(array[mid:])


  i,j,k=0,0,0

  while i<len(left) and j<len(right):
    if left[i]<right[j]:
      array[k]=left[i]
      i+=1
    else :
      array[k]=right[j]
      j+=1
    k+=1


  if i==len(left):
    while j<len(right):
      array[k]=right[j]
      j+=1
      k+=1
  elif j==len(right) :
    while i<len(left):
      array[k]=left[i]
      i+=1
      k+=1

  return array



# 데이터 입력
N=int(input())
#N=5
#lst=[4,2,2,6,1]
lst=[]

for _ in range(N):
  lst.append(int(input()))

lst=merge_sort(lst)

for i in lst:
  print(i)

재귀함수를 이용해서 1개의 리스트로 쪼개진 다음 다시 정렬되면서 합쳐지는 방식이다.

 

아래의 블로그를 통해 공부했다.

https://assaeunji.github.io/python/2020-05-06-bj2751/

[백준] 2751 수 정렬하기 2 파이썬 풀이

https://blog.naver.com/ndb796/221227934987

7. 병합 정렬(Merge Sort)