[Udemy] 병합 정렬(Merge Sort)이란?

정의

말 그대로 Merge + Sorting을 실행하는 정렬 방법이다.

사실은 분할(Split) → 정렬(Sort) → 병합(Merge)이 과정으로 진행한다.

배열 길이가 1이하면 정렬되었다고 가정한다.

접근

분할과 정렬 + 병합 이렇게 2단계로 나눠서 접근해보자.

1. 정렬 + 병합

정렬 + 병합은 첫번째 배열과 두번째 배열을 비교하면서 정렬을 하면서 하나의 배열로 병합하는 로직이 필요하다.
이는 앞서 배웠던 Two Pointer 패턴을 사용하면 쉽게 구현할 수 있다.

1. 인수로 전달 받은 두 배열은 정렬된 배열임을 가정하고 결과 배열을 선언한다.

왜냐하면, 배열의 길이가 1이하인 것부터 정렬 + 병합하면서 진행할 것이기 때문이다.

2. 첫번째 배열 포인터 i, 두번째 배열 포인터 j 선언하여 둘 중 하나의 포인터가 배열을 순회하면 종료한다.

순회 시 비교해야할 것은 각 배열의 현재 포인터의 값이다.
만약 첫번째 배열 포인터에 위치한 값이 두번째 배열 포인터에 위치한 값보다 크다면,
오름차순 정렬을 기준으로 하기 때문에 두번째 배열 값을 결과 배열에 push한다.
이 때, 두번째 배열의 포인터 j 값을 1 증가 시킨다.

이를 반복 순회하다가 포인터가 배열의 길이와 동일해졌을 때 순회를 중단한다.

3. 순회 중단 후 아직 결과 배열에 추가되지 못하고 남은 요소들을 결과 배열에 추가한다.

function merge(arr1, arr2) {
  let result = [];
  let i = 0;
  let j = 0;

  while (arr1.length > i && arr2.length > j) {
      if (arr2[j] > arr1[i]) {
      result.push(arr1[i]);
      i++;
    } else {
      result.push(arr2[j]);
      j++;
    }
  }

  if (arr1.length > i) {
    result.push(...arr1.slice(i));
  } else if (arr2.length > j) {
    result.push(...arr2.slice(j));
  }

  return result;
}

2. 분할 및 mergeSort 구현

두 배열을 비교하여 정렬 + 병합하는 merge함수는 완성했다.
이제 남은 것은 merge함수를 언제 어떻게 호출하여 결과값을 얻어내는가? 이다.

주어진 배열이 [1,20,15,12]라고 가정해보자.

1. mergeSort에서 주어진 배열을 절반으로 left, right 나눠서 mergeSort를 재귀 호출한다.
2. mergeSort에 주어진 배열의 길이가 1 이하일 때 까지 재귀호출한다.
3. 마침내  배열 길이가 1이하 이면, left, right를 merge 호출한 값을 반환한다.

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);
}

 

시간 복잡도

 

시간 복잡도가 O(n^2)보다 개선된 성능을 가지고 있다. 단, 시간 복잡도가 향상되었지만, 공간복잡도가 다른 정렬보다 성능이 하락했으므로 메모리를 고려해야할 경우 이 또한 고려할 부분이다.

 

O(n log n)이 나온 이유는 배열 길이가 32라고 가정할 때,

 

32

16 16

8 8 8 8

4 4 4 4 4 4 4 4

...

 

n = 32이면 5번 뎁스를 타고 가므로 이는 log N의 시간복잡도를 의미한다.

여기에 각 분할마다 병합할 때 merge 함수에서 비교할 때, O(n)이 추가된다.

따라서 병합 정렬의 시간복잡도는 O(n log n)이 된다.

 

참조

Udemy - Js 알고리즘 & 자료구조 강의