[알고리즘 with JS] 병합 정렬(Merge Sort)이란?

 

병합 정렬에 대해 알아보겠습니다.

 

 

🧑🏻‍💻 병합 정렬 (Merge Sort) 

 

병합 정렬은 존 폰 노이만(John von Neumann)이라는 사람이 제안한 방법입니다.

 

이 알고리즘을 사용하면 O(n^2)에서 O(nlogn)까지 시간 복잡도를 개선할 수 있습니다.  일반적인 방법으로 구현했을 때 이 정렬은 분할 정복 알고리즘의 하나입니다. 

 

📌 분할 정복(divide and conquer) 

문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략입니다.

분할 정복 방법은 대개 순환 호출을 이용하여 구현합니다. 

 

 

⭐️ 과정 설명 

- 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 봅니다. 

- 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눕니다.

- 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬합니다. 

- 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병합니다.

 

📌 합병 정렬 알고리즘의 개념 

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법입니다.

 

합병 정렬은 다음의 단계로 이루어집니다.

 

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

- 정복(Conquer): 부분 배열을 정렬합니다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용합니다. 

- 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병합니다.

 

 

 

📌 Merge Arrays

- 병합 정렬을 구현하려면 먼저 두 개의 정렬된 배열을 병합하는 기능을 구현해야 합니다.

- 정렬된 두 개의 배열이 있는 경우 이 도우미 함수는 역시 정렬된 새 배열을 생성해야 하며 두 입력 배열의 모든 요소로 구성됩니다.

- 이 함수는 O(n+m) 시간과 O(n+m) 공간에서 실행되어야 하며 전달된 매개변수를 수정해서는 안됩니다. 

 

 

📌 Merge Arrays Pseudocode 

- 빈 배열을 만들고, 각 입력 배열에서 가장 작은 값을 가져옵니다. 

- 첫 번째 배열의 값이 두 번째 배열의 값보다 작은 경우 첫 번째 배열의 값을 결과에 푸시하고 첫 번째 배열의 다음 값으로 이동합니다.

- 첫 번째 배열의 값이 두 번째 배열의 값보다 크면 두 번째 배열의 값을 결과에 푸시하고 두 번째 배열의 다음 값으로 이동합니다.

- 하나의 배열이 소진되면 다른 배열의 나머지 값을 모두 푸시합니다. 

 

// 기본 logic 
const merge = (arr1, arr2) => {
  let 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;
};

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

 

 

📌 MergeSort Pseudocode 

- 배열이 비어 있거나 하나의 요소를 가질 때까지 배열을 반으로 나눕니다. 

- 더 작게 정렬된 배열이 있으면 배열의 전체 길이로 돌아올 때까지 해당 배열을 다른 정렬된 배열과 병합합니다.

- 배열이 다시 병합되면 정렬된 배열을 반환합니다.

 

const merge = (arr1, arr2) => {
  let 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;
};

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

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