Udemy - 병합 정렬

---

병합 정렬?

1948년 수학자 조나단 벤자민 뉴이맨이 만든 알고리즘이다.
널리 알려져있고, 매우 빠른 속도를 자랑하는 정렬 알고리즘 중 하나이다.

분할점령 접근법을 활용한다.

이전에 분할점령(Divide and Conquer)을 활용해본적이 있다. 분할점령은 배열을 쪼개가며 특정 값을 빠르게 찾아나가는 알고리즘이었는데, 병합 정렬 또한 비슷한 접근법을 취한다.

우선, 초기 배열을 이등분하고, 지속적으로 배열이 개별 원소들로 쪼개질 때 까지 n등분한다. 그리고 다시 원소들을 단계별로 병합하며 작은 수부터 정렬해 나가는 것이다. 사실 글로 표현하기엔 다소 어려운 부분이기에 아래의 시각자료를 보면 쉽게 이해할 수 있을 것이다.

---

병합을 하는 방법 (step1)

분할을 해서 가장 작은 단위로 만들고, 점점 조합(병합)해 나가며 정렬하겠다는 것은 알겠다.
그렇다면 그 병합은 어떻게 이루어지는 걸까?

기본 병합 예제

주어진 정렬된 두 배열을 병합하여 완전히 정렬된 배열로 만들기

function merge(arr1, arr2) {
  let answer = [];
  let i = 0;
  let j = 0;
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      answer.push(arr1[i]);
      i++;
    } else {
      answer.push(arr2[j]);
      j++;
    }
  }
  while (i < arr1.length) {
    answer.push(arr1[i]);
    i++;
  }
  while (j < arr2.length) {
    answer.push(arr2[j]);
    j++;
  }
  return answer;
}

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

---

병합 정렬 알고리즘 구현 (step2)

위의 병합 알고리즘과 재귀 알고리즘을 합치면 병합 정렬 알고리즘을 구현할 수 있다.

function mergeSort(arr) {
  // 병합 알고리즘 파트 (비교와 정렬이 일어남)
  const merge = (arr1, arr2) => {
    let answer = [];
    let i = 0;
    let j = 0;
    while (i < arr1.length && j < arr2.length) {
      if (arr1[i] <= arr2[j]) {
        answer.push(arr1[i]);
        i++;
      } else {
        answer.push(arr2[j]);
        j++;
      }
    }
    while (i < arr1.length) {
      answer.push(arr1[i]);
      i++;
    }
    while (j < arr2.length) {
      answer.push(arr2[j]);
      j++;
    }
    return answer;
  };
  // 병합 정렬 재귀 알고리즘 파트 (실질적으로 분할이 일어나는 곳)
  // 1. endpoint를 지정해준다.
  if (arr.length <= 1) return arr;
  // 2. 분할을 위해 중간값, 좌측 배열, 우측 배열을 선언해준다.
  let mid = Math.floor(arr.length / 2);
  // 0~mid까지 => 계속 콜스택에 쌓아 끝까지 분할하기 위해 재귀호출
  let left = mergeSort(arr.slice(0, mid));
  // mid~끝까지
  let right = mergeSort(arr.slice(mid));
  // left와 right가 각각 정립되면 merge 함수를 호출해 병합하고 정렬해준 값을 리턴해준다.
  return merge(left, right);
}

---

시간복잡도와 공간복잡도

1. 시간 복잡도 : O(nlogn)
2. 공간 복잡도 : O(n)

---