python으로 쉽게 설명하는 merge sort algorithm(합병 정렬)

합병 정렬 알고리즘은 대표적인 분할 정복 알고리즘 종류 중 하나이다.

 

 

내가 작성한 파이썬 코드로 쉽게 알아보자.

 

 

import numpy as np

def merge(n):
    if len(n) < 2:
        print (n)
    else:
        half = len(n) // 2
        left_n = n[:half] # 배열을 왼쪽, 오른쪽 반으로 나눠주자
        right_n = n[half:]
        
        print(left_n) 
        print(right_n)

        sorted_left_n = sorted(left_n) # 반으로 나눈 걸 각각 정렬해주자
        sorted_right_n = sorted(right_n)
        
        print(sorted_left_n)
        print(sorted_right_n)

        merged_n = np.concatenate([sorted_left_n, sorted_right_n]) # 정렬이 완료된 왼쪽, 오른쪽 배열을 다시 합치자.
        print(sorted(merged_n)) # 합병 정렬 완료


N = list(map(int, input().split(' ')))

merge(N)

 

순서

 

 

우선 합병 정렬 알고리즘은 순서가 나뉘어져 있다.

 

 

전체 데이터 배열의 길이를 반으로 나눠 왼쪽, 오른쪽 배열로 나눠준다.

 

 

---

 

예로 [4, 2, 7, 8, 1, 9] 라는 배열이 존재한다고 가정해보자

 

 

그럼 우선 해야할 일은 이걸 반으로 나눠줘야 한다

[4, 2, 7] [8, 1, 9] 이렇게

 

 

그런 다음 나눈 걸 정렬해주자.

왼쪽 [4, 2, 7] 배열은 [2, 4, 7] 

오른쪽 [8, 1, 9] 배열은 [1, 8, 9]

 

 

* 아 이제와서 참고로 말하지만 파이썬에서는 오름차순 정렬하려면 위에 있는 코드처럼 하지 말고 그냥 sorted함수 사용하면 다 알아서 정렬해준다. 내가 코드를 일부러 길게 작성한 이유는 가시적으로 쉽게 설명하기 위해 일부러 일일이 다 작성하였다.

 

 

다 정렬이 완료되었다면, 이 두개의 배열을 다시 합쳐주는 동시에 정렬시키자.

[2, 4, 7] + [1, 8, 9] = [1, 2, 4, 7, 8, 9]

 

 

---

 

 

코드의 결과로 나타내면 다음과 같다.

 

 

 

그럼 정렬 끝!

 

---

시간 복잡도

 

 

합병 정렬 알고리즘의 시간 복잡도는 O(n log n)이다.

 

 

위의 배열을 계속해서 예를 들어보면,

우선 n의 개수는 6개로 6개의 반(3)을 또 반(1.5)으로 나눠서 정렬하기 때문에 우선 log n의 시간이 걸리고

 

 

마지막에 배열을 합치며 정렬할 때는 모든 요소를 확인하기 때문에 n의 시간이 걸린다

 

 

따라서 복잡도는 log n과 n을 합쳐서 -> O(n log n)

 

 

 

 

끝!