알고리즘 - merge sort (합병정렬)

합병 정렬(merge sort)란?

 

모여있는 데이터들을 요소가 단 1개가 될 때까지 계속 반으로 나누다가 1개로 나눠지면 그때부터 역으로 숫자를 1개씩 정렬하면서 올라가고 병합하는 방식

 

예를 들자면 다음과 같다.

 

7, 4, 5, 2, 6, 3, 8, 1


7 | 4 | 5 | 2 | 6 | 3 | 8 | 1 → 가장 작은 부분 (숫자 1개)으로 나눠진 결과


4   7 | 2   5 | 3   6 | 1   8 → 숫자 1개씩을 정렬하여 병합한 결과


2   4   5   7 | 1   3   6   8 → 숫자 2개씩을 정렬하여 병합한 결과


1   2   3   4   5   6   7   8 → 마지막으로 숫자 4개씩을 정렬하여 병합한 결과

 

1. 우선적으로 숫자들을 각 요소가 1개가 될 때까지 계속 쪼갠다.

2. 2개의 데이터를 묶어서 비교해서 큰 수는 오른쪽, 작은 수는 왼쪽으로 오도록 병합한다.

3. 그리고 이걸 계속 반복한다.

 

합병정렬은 버블이나 선택 정렬에 비해서 빠르다.

 

합병 정렬의 상한 시간은 O(n log n)이고 하한 시간도 ΩO(n log n)이다.