병합 정렬 : 자르고 합치기

이번 포스팅에서는 Merge sort - 병합 정렬에 대해 알아보도록 하겠습니다.

---

1. 병합 정렬 (Merge Sort) 이란?

이름에서 알 수 있듯이 병합정렬은 주어진 자료구조를 여러 조각으로 자르고 다시 합쳐 나가는 과정에서 정렬을 하는 정렬입니다. 구현 방식은 일반적으로 재귀로 구현되며 분할정복 방식이라는 데서 Quick Sort와 유사한 면이 있어 자주 비교 대상이 되곤 합니다.

 

퀵 정렬 : Pivot

 

---

 

2. 병합 정렬의 진행

1. 자료 구조의 길이가 0 또는 1이면 이미 정렬 된것으로 봅니다. ( 기저 조건 )
2. 그렇지 않은 경우 자료구조를 절반으로 잘라 두 부분의 자료구조로 나눕니다.
3. 각 부분 자료구조를 병합 과정을 통해 정렬 합니다.
4. 정렬을 마친 부분 자료구조를 하나의 자료구조로 병합합니다.

 

위에서 말한 실제 정렬이 발생하는 병합 과정에 대해 자세히 설명하겠습니다.

1. 두 개의 부분 자료구조의 값을 첫 원소부터 차례대로 비교하여 더 작은 값을 빼내어 새로운 자료구조로 옮깁니다.
2. 두 개의 부분 자료구조 중 어떤 것이든 원소가 더 이상 존재하지 않을 때까지 1번 동작을 반복합니다.
3. 두 개 중 하나가 끝나게 되면 남은 나머지 자료구조에 있는 원소들을 모두 새로운 자료구조로 옮깁니다
4. 새로운 자료구조를 반환합니다.

 

---

 

3. 병합 정렬의 코드 구현

function mergeSort(array) {
    // 기저 조건
    if (array.length === 1) return array;
    // 두 개의 배열로 분리할 기준점 (배열의 정중앙)
    const boundary = Math.ceil(array.length / 2);
    // 좌측 부분 배열
    const left = array.slice(0, boundary);
    // 우측 부분 배열
    const right = array.slice(boundary);
    // 재귀 호출 하며 반환된 값들을 병합하며 반환
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    // 정렬 상태의 새로운 자료구조
    const sortedArray = [];
    // 두 개의 자료구조 중 어느 한쪽의 원소가 존재하지 않을 때까지
    while (left.length && right.length) {
        // 좌측 자료구조의 가장 앞 원소가 더 작다면
        if (left[0] <= right[0]) {
            // 좌측 자료구조의 해당 원소를 제거해 새로 생성한 자료구조에 삽입
            sortedArray.push(left.shift());
        } else {
            // 우측 자료구조의 가장 앞 원소가 더 작다면
            // 우측 자료구조의 해당 원소를 제거해 새로 생성한 자료구조에 삽입
            sortedArray.push(right.shift());
        }
    }
    // 나머지 남은 원소들을 삽입하며 정렬된 자료구조 반환
    return [...sortedArray, ...left, ...right];
}

 

---

 

4. 병합 정렬의 효율성

• 시간 복잡도
  • 한 깊이에서 모든 원소에 대한 비교연산 $ N $ 회  * 병합 연산의 횟수 ( 깊이 ) $ logN $ 회 
  • 모든 상황에서 $ O(NlogN) $입니다.

• 공간 복잡도
  • 병합 과정에서 별도의 정렬된 상태의 원소들을 저장할 자료구조가 필요하기 때문에 $ O(N) $ 입니다.

 

---

 

4. 병합 정렬의 특징

• 병합의 대상이 되는 두 자료구조가 항상 정렬이 되어있기 때문에 순차적 비교로 정렬할 수 있습니다.
• 순차적 비교이기 때문에  연결리스트에서 효율적으로 사용될 수 있습니다.
  • 퀵 정렬의 경우 임의 접근을 사용하기 때문에 비효율적
• 안정 정렬입니다.
• 퀵 정렬이 정렬 => 분할이라면 병합 정렬은 분할 => 정렬이라 할 수 있습니다.