[Algorithm] 병합 정렬 (Merge Sort)

병합 정렬 (Merge Sort)

합병 정렬이라고도 부르며, 이 정렬은 안정 정렬에 속하며, 분할 정복 기법과 재귀 용법을 활용한 정렬 알고리즘이다.

* [분할 정복(divide and conquer) 방법]
큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식.
문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.

병합 정렬은 정렬할 원소 목록을 원소가 하나 밖에 남지 않을 때까지 절반으로 잘라 비슷한 크기의 두 부분으로 계속 나눈다. 정렬할 때는 각 절반의 가장 작은 요소를 비교하여 수행된다. (각 목록의 첫 번째 요소가 가장 먼저 비교된다.) 더 작은 값으로 시작되는 것을 정렬된 목록에 추가한다.

 

프로세스

• 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.
• 그렇지 않은 경우에는, 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
• 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
• 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

 

ex)

• 2개의 정렬된 리스트를 합병(Merge)하는 과정
  1. 2개의 리스트의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트(sorted)로 옮긴다.
  2. 둘 중에서 하나가 끝날 때까지 이 과정을 되풀이한다.
  3. 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 값들을 전부 새로운 리스트(sorted)로 복사한다.
  4. 새로운 리스트(sorted)를 원래의 리스트(list)로 옮긴다.
• 합병 정렬의 과정
  • 추가적인 리스트가 필요하다.
  • 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.
  • 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계이다.

단계 정리

하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.

합병 정렬은 다음의 단계들로 이루어진다.

• 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.

const mergeSort = array => {
  if (array.length < 2) return array; // 원소가 하나일 때는 그대로 내보냅니다.
  
  let pivot = Math.floor(array.length / 2); // 대략 반으로 쪼개서 pivot을 정한다.
  let left = array.slice(0, pivot); // 쪼갠 왼쪽
  let right = array.slice(pivot); // 쪼갠 오른쪽
  
  return merge(mergeSort(left), mergeSort(right)); // 재귀적으로 쪼개고 합친다.
}

• 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 재귀적 호출(순환 호출) 을 이용하여 다시 분할 정복 방법을 적용한다.
• 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.

const merge = (left, right) => {
  let sorted = [];
  
  while (left.length && right.length) {
    if (left[0] <= right[0]) // 두 배열의 첫 원소를 비교하여
      sorted.push(left.shift()); // 더 작은 수를 결과에 넣어줍니다.
    else
      sorted.push(right.shift()); // 오른쪽도 마찬가지
  }

  return [...sorted, ...left, ...right]; // 아래 코드와 기능 동일
  
  // while (left.length) sorted.push(left.shift()); // 어느 한 배열이 더 많이 남았다면 나머지를 다 넣어줍니다.
  // while (right.length) sorted.push(right.shift()); // 오른쪽도 마찬가지
  // return sorted;
};

 

Quick Sort와의 차이점

퀵 정렬 : 우선 피벗을 통해 정렬(partition) → 영역을 쪼갬(quickSort)

병합 정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) → 정렬(merge)

요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식으로, 쪼개는 방식은 퀵 정렬과 유사.

병합 정렬은 이미 합병의 대상이 되는 두 영역이 각 영역에 대해서 정렬이 되어있기 때문에 단순히 두 배열을 순차적으로 비교하면서 정렬할 수가 있다.

병합 정렬은 순차적인 비교로 정렬을 진행하므로, Linked List의 정렬이 필요할 때 사용하면 효율적이다.

Linked List를 퀵 정렬을 사용해 정렬하면?

• 성능이 좋지 않다.
• 퀵정렬은 순차 접근이 아닌 임의 접근이기 때문이다.

Linked List는 삽입, 삭제 연산에서 유용하지만 접근 연산에서는 비효율적이다.

따라서 임의로 접근하는 퀵 정렬를 활용하면 오버헤드 발생이 증가하게 됨

배열은 인덱스를 이용해서 접근이 가능하지만, Linked List는 Head부터 탐색해야 함
배열[O(1)] vs Linked List[O(n)]

 

시간복잡도

평균	최선	최악
Θ(nlog₂n)	Ω(nlog₂n)	O(nlog₂n)

• 비교 횟수 (log₂n)
  •  순환 호출의 깊이 (합병 단계의 수)
    • 레코드의 개수 n이 2의 거듭제곱이라고 가정(n=2^k) 했을 때, n=2^3의 경우, 2^3 -> 2^2 -> 2^1 -> 2^0 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다. 이것을 일반화하면 n=2^k의 경우, k(k=log₂n) 임을 알 수 있다.

• 각 합병 단계의 비교 연산
  
  • 크기 1인 부분 배열 2개를 합병하는 데는 최대 2번의 비교 연산이 필요하고, 부분 배열의 쌍이 4개이므로 2*4=8번의 비교 연산이 필요하다.
  • 다음 단계에서는 크기 2인 부분 배열 2개를 합병하는 데 최대 4번의 비교 연산이 필요하고, 부분 배열의 쌍이 2개이므로 4*2=8번의 비교 연산이 필요하다.
  • 마지막 단계에서는 크기 4인 부분 배열 2개를 합병하는 데는 최대 8번의 비교 연산이 필요하고, 부분 배열의 쌍이 1개이므로 8*1=8번의 비교 연산이 필요하다.
  • 이것을 일반화하면 하나의 합병 단계에서는 최대 n번의 비교 연산을 수행함을 알 수 있다.

비교 횟수 : 순환 호출의 깊이 만큼의 합병 단계 * 각 합병 단계의 비교 연산 = nlog₂n

• 이동 횟수
  • 순환 호출의 깊이 (합병 단계의 수)
    
    • k=log₂n
  • 각 합병 단계의 이동 연산
    
    • 임시 배열에 복사했다가 다시 가져와야 되므로 이동 연산은 총 부분 배열에 들어 있는 요소의 개수가 n인 경우, 레코드의 이동이 2n번 발생한다.
  • 순환 호출의 깊이 만큼의 합병 단계 * 각 합병 단계의 이동 연산 = 2nlog₂n

T(n) = nlog₂n(비교) + 2nlog₂n(이동) = 3nlog₂n = O(nlog₂n)

 

장점

• 안정적인 정렬 방법
  • 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. (nlog₂n로 동일)
  • 항상 동일한 시간이 소요되므로 어떤 경우에도 좋은 성능을 낼 수 있다.
• 퀵 정렬과 달리 기준값(pivot)을 설정하는 과정이 없어 기준값에 따라 성능이 달라지는 경우가 없다.
• 만약 데이터를 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
  
  • 제자리 정렬(in-place sorting)로 구현할 수 있다.
  • 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 졍렬 방법보다 효율적이다.

단점

• 만약 데이터를 배열(Array)로 구성하면, 임시 배열이 필요하다.
  
  • 제자리 정렬(in-place sorting)이 아니다.
  • 임시배열에 원본을 계속해서 옮기며 정렬을 하는 방식이기 때문에 추가적인 메모리가 필요하다.
• 배열의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.

 

정렬 알고리즘 시간복잡도 비교

• 단순(구현 간단)하지만 비효율적인 방법
  • 삽입 정렬, 선택 정렬, 버블 정렬
• 복잡하지만 효율적인 방법
  • 퀵 정렬, 힙 정렬, 병합 정렬, 기수 정렬