🗂️ 자료구조 공부하기 4 | 병합 정렬(merge sort)

 

병합 정렬(merge sort)

 

병합 정렬 또는 합병 정렬은 비교 기반의 정렬 알고리즘이다.

 

 

위키피디아 이미지

 

 

예를 들어, 정렬된 두 개의 배열이 있다고 하자. 

let arr1 = [4,6,7,8];
let arr2 = [1,5,6,7];
let result = [];

 

정렬된 두 배열을 하나의 배열로 합치기 위해서는 어떻게 해야할까?

 

가장 빠른 방법은 이미 두 배열이 정렬된 상태이기 때문에 가장 작은 값끼리 비교를 하는 것이다. 여기서 말하는 가장 작은 값은 0번째 인덱스에 위치한 원소이다. 

 

처음에는 4와 1을 비교하는데 1이 4보다 작으므로 result에 1이 먼저 들어가게 된다.  

4 > 1

result.push(1);

 

그 다음 비교대상은 4와 1의 다음 숫자인 5이다. 

4 < 5

result.push(4);

 

더 작은 숫자인 4가 들어가게 되고 이 과정을 계속 반복하게 되면 정렬된 배열을 리턴하게 된다. 

console.log(result);

//[1,4,5,6,6,7,7,8];

 

 

 

 

 

그럼 이번엔 정렬되지 않은 하나의 배열을 하나로 합쳐보자

 

아까와 같은 방법으로 정렬하기 위해서는 일단 하나의 배열을 2개로 나누어야 한다. 

let arr = [4,6,2,3,8,1,9,7]

let leftArr = [4,6,2,3];
let rightArr = [8,1,9,7];

 

leftArr, rightArr를 또 다시 두개로 나눈다. 그리고 그 과정을 반복한다.

이제 원소가 나눠졌다면, 두개가 한 쌍을 이루어서 정렬되면 된다. 

정렬된 것들을 다시 두 묶음씩 해서 정렬된 두 배열을 정렬해주면 된다!

 

 

 

 

머지 소트의 시간복잡도는 어떻게 될까?

 

 

 

n개의 요소를 log n번 재귀를 돌리기 때문에 O(nlogn)의 시간복잡도를 갖게 된다. 

log n 은 처음 8개의 요소에서 4개씩, 2개씩 이렇게 탐색해야하는 데이터가 절반씩 줄어들기 때문이다. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

[참고자료]