알고리즘 - 병합 정렬(Merge sort)이란?

병합 정렬 알고리즘의 개념

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

- 병합 정렬은 3 단계를 거친다.

1. 분할 : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.

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

3. 결합 : 정렬된 부분 배열들을 하나의 배열에 합병한다. 

즉, 데이터가 하나 남을 때까지 반복한다. 그 후에 하나씩 쪼개진 데이터졍렬을 하면서 다시 그룹화를 한다.

분할 정복의 짤

 

시간 복잡도는 O(n log2n)이다. 좋을 때나 나쁠 때나 속도는 같다. 하지만 단점으로는 메모리 공간이 필요하기 때문에 메모리 공간이 없다면 퀵 정렬을 사용하는게 낫다. 

 

function mergeSort(arr) {
  if (arr.length < 2) {
    // 배열이 나눠지다가 하나만 남았을 땐 배열 자체를 리턴
    return arr;
  }

  const mid = Math.floor(arr.length / 2); // 배열 길이의 반을 기준으로 왼쪽과 오른쪽을 나눈다.

  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  console.log(left, right);
  return merge(mergeSort(left), mergeSort(right)); // 분열 시작 왼쪽과 오른쪽을 서로 의 길이가 1이 될 때 까지 분할
}

function merge(left, right) {
  const result = [];

  while (left.length !== 0 && right.length !== 0) { // 재귀
    // 이제 길이가 2이상인 배열들이 각각 서로의 크기를 비교해서 작은 숫자 먼저 result에 들어간다.
    left[0] <= right[0]
      ? result.push(left.shift())
      : result.push(right.shift());
  }
  console.log(result);
  while (left.length) {
    // 왼쪽과 오른쪽 중 남은 배열이 있다면 그 배열을 그대로 뒤에 붙여준다.
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }

  return result;
}

const arr = [6, 7, 8, 3, 1, 2, 3, 4, 5, 10, 15, -1, 0];

const result = mergeSort(arr);
console.log(result);

 

 

 

 

 

 

참고 - 

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

https://im-developer.tistory.com/134

[JS/Sorting] 병합 정렬(Merge Sort)과 분할 정복 전략(Divide and Conquer) 개념에 대하여