sungyup's.

javascript_algorithm / 정렬 알고리즘 / 3.7 Merge Sort

3.7Merge Sort

병합 정렬의 원리와 JavaScript 구현

TL;DR

추억의 쪽지 시험

Merge Sort

1948년에 존 폰 노이만이 만든 방식으로, 정렬된 배열들 및 요소가 적은 배열들이 보다 정렬하기 쉽다는 것을 이용한다.

  1. 배열을 계속 반으로 쪼개어 요소가 0개 또는 1개가 될 때까지 나눈다.
  2. 그런 다음, 정렬된 두 배열을 병합하며 점점 더 큰 정렬된 배열을 만든다.

이 과정은 Divide and Conquer(분할 정복) 전략에 기반한다.

정렬된 배열 병합하기 (Merging Arrays)

우선 두 개의 정렬된 배열들이 있을 때, 이 둘을 하나의 정렬된 배열로 합치는 과정을 생각해보자.

  1. 빈 배열을 만들고, 각 배열들의 왼쪽에 각각 포인터 i와 j를 둔다.
  2. 이 중 더 작은 값을 빈 배열에 넣고(각각의 배열은 정렬된 배열이므로 값은 두 배열에서 최소값이다)하고, 더 작은 값을 찾은 배열의 포인터에 +1을 해준다.
  3. 끝까지 반복한다. 이 과정에서, 한 쪽 배열이 먼저 끝에 도달할텐데 남은 배열의 남은 요소는 그대로 끝까지 새로 만든 배열에 추가한다.
javascript
function merge(arr1, arr2){
  const results = [];
  let i = 0;
  let j = 0;
  while(i < arr1.length && j < arr2.length){
    if(arr2[j] > arr1[i]){
      results.push(arr1[i]);
      i++;
    } else {
      results.push(arr2[j]);
      j++
    }
  }
  while(i < arr1.length){
    results.push(arr1[i]);
    i++;
  }
  while(j < arr2.length){
    results.push(arr2[j]);
    i++;
  }

  return results;
}

merge([1, 10, 50], [2, 14, 99, 100]);

Merge Sort 구현

다음으로 배열을 빈 배열 또는 요소가 하나인 배열로 나누는 과정을 생각해보자. 전체 배열을 모두 요소가 하나 또는 빈 배열로 나누려면 재귀적으로 코드를 작성하면 된다.

javascript
function mergeSort(arr){
  if(arr.length <= 1) return arr;
  let mid = Math.floor(arr.length / 2);
  // 재귀적으로 왼쪽/오른쪽 부분을 나눈다.
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid));
  // 나뉜 배열들을 합한다.
  return merge(left, right);
}

Merge Sort의 Big O

Merge Sort의 시간 복잡도는 배열이 어떻든 간에 O(n log n)이다. 이유는, 우선 배열들을 두개로 재귀적으로 계속 나누는 과정에서 log n이 걸리고 이후 n개의 배열들을 비교하며 정렬하기 때문이다.

O(n log n)은 배열이 특수한 경우가 아니라면 정렬 알고리즘에서 얻을 수 있는 최선의 결과다.

배열들을 n개로 나누기 때문에 공간 복잡도는 항상 O(n)이다.

PreviousQuick Sort
Algorithm
NextRadix Sort
Algorithm