JavaScript로 알아보는 병합 정렬(Merge Sort)과 예제 코드

소개

병합 정렬(Merge Sort)은 대표적인 분할 정복(Divede and Conquer) 알고리즘 중 하나로, 리스트를 반으로 나눈 뒤 각각을 재귀적으로 정렬하고, 정렬된 두 개의 리스트를 합쳐서 정렬된 하나의 리스트를 만드는 알고리즘입니다.

작동 개념💡

병합 정렬은 일반적으로 다음과 같은 세 단계로 구성됩니다.

1. 분할(Divide): 입력 리스트를 같은 크기의 두 개의 부분 리스트로 분할합니다. 이때 분할은 리스트의 중간 지점에서 수행됩니다.
2. 정복(Conquer): 각 부분 리스트를 재귀적으로 병합정렬을 이용해 정렬합니다. 이 과정은 입력 리스트의 크기가 충분히 작아질 때까지 반복됩니다.
3. 병합(Merge): 정렬된 두 부분 리스트를 하나의 정렬된 리스트로 병합합니다.

• 0개 요소, 1개 요소 배열이 이미 정렬되어 있다는 점을 활용합니다.
• 배열을 더 작은 배울려 나누는 방식입니다.
• 분할 정복 알고리즘이라 알려진 방식이고, 더 큰 배열을 나누고, 더 작은 하위 배열로 정렬합니다.
• 배열의 요소가 0 또는 1개가 될 때까지 반복합니다.
• 계속 분할한 다음 다시 병합시킵니다.

배열을 병합하는 코드

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]);
    j++;
  }

  return results;
}

1. 입력 두 개를 취하는 함수를 정의하여 빈 배열을 만들고, 마지막에 반환할 빈 배열을 만듭니다.
2. 각 입력 배열에서 가장 작은 값(처음)부터 시작합니다.
3. i와 j 두 개의 카운터가 있습니다. 이 카운터들은 0부터 시작합니다.
4. 아직 살펴보지 않은 값이 있다면, 즉 i와 j가 각각의 배열 끝에 도달하지 않았다면
   1. 첫 번째 배열의 값으로 첫 번째 항목을 취한 다음 두 번째 배열의 첫 번째 항목 값과 비교합니다.
   2. 첫 번째 항목이 더 작다면 results 배열에 넣고 다음 첫 번째 배열의 다음 항목으로 넘어갑니다.
   3. 반대로 첫 번째 배열에 있는 항목이 더 크다면 두 번째 배열의 값을 취하여 results 배열에 넣은 다음 두 번째 배열의 다음 값으로 넘어갑니다
5. 배열 하나를 완료한 다음에는 다른 배열의 남은 값을 모두 넣습니다.

병합정렬 구현 코드

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

console.log(mergeSort([10, 24, 76, 73])); // [10, 24, 73, 76]

1. 배열의 길이가 1또는 0이 될 때까지 mergeSort 함수를 호출합니다.
2. 배열의 절반을 자르기 위해서 mid라는 변수에 배열 길이 / 2의 내림 값을 저장합니다.
3. 왼쪽 절반과 오른쪽 절반을 slice 메서드를 통해서 나눠줬는데, 이들에게 mergeSort를 호출해 줍니다.

시간 복잡도 

최고	평균	최악	공간 복잡도
O(n log n)	O(n log n)	O(n log n)	O(n)

계속 나누고 나눈 다음 합치고 또 합칠 뿐이기 때문에 병합 정렬에서는 예외 케이스가 없습니다.

 

O(log n)은 만약 32개의 요소가 있다면 2x2x2x2x2라는 의미인데, n log n은 각 분할마다, 병합할 때 O(n)번 비교합니다.

n의 길이가 늘어난다면, 병합 정렬이 아닌 병합 알고리즘 자체는 O(n)의 시간 복잡도를 갖게 되는데 그래서 종합적으로 보면 병합 정렬의 Big O는 O(n log n)이 됩니다.

정리하자면 log n은 n증가에 따르는 분할 수입니다.

n에 따라 분할할 횟수를 말하고, 배열이 늘어나면 log n 비율로 늘어난다.
병합을 실제로 수행하려면 O(n) 비교가 필요하고 결과적으로는 총 O(n log n)이 됩니다.