[JS] 병합정렬

 

1. 소개

병합정렬은 대표적은 분할정복 알고리즘 중 하나로, 리스트를 반으로 나눈 뒤 각각을 재귀적으로 정렬하고, 정렬된 두 리스트를 합쳐 하나의 리스트를 만드는 알고리즘 이다.

 

2. 작동개념

일반적으로 세 단계로 구성된다.

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

 

3. 시간 복잡도

O(n log n) 

계속 나누고 나눈 다음 합치고 또 합칠 뿐이기 때문에 병합 정렬은 예외 케이스가 없다.(안정성)

 

4. 구현

2가지 함수를 이용해 구현할 수 있다.

• mergeSort(arr) : 반으로 나누어 주는 함수
• merge(left,right) : 반으로 나누어 준 함수를 갖고 정렬해 새로운 배열로 만들어주는 함수
  (이 과정에서 새로운 배열로 만들어 주기 때문에 메모리가 필요하다.)

function merge(left, right) {
  const sortedArr = [];
  while (left.length && right.length) {
    //left[0]이 더작을 경우 같을때는 누가 먼저 들어가도 상관X
    if (left[0] <= right[0]) {
      sortedArr.push(left.shift());
    } else {
      sortedArr.push(right.shift());
    }
  }
  //left,right 둘 중 하나는 요소가 남아있기 때문에 sortedArr 뒤에 붙여서 출력
  //비어있으면 spread Syntax에도 아무것도 없기 때문에 그냥 다 붙여준다.
  return [...sortedArr, ...left, ...right];
}

function mergeSort(arr) {
  if (arr.length === 1) return arr;
  const boundary = Math.ceil(arr.length / 2);
  //slice로 해주기 때문에 원본 arr은 손상 없다.
  const left = arr.slice(0, boundary);
  const right = arr.slice(boundary);
    //요소가 1개 일 때까지 재귀를 실행해 요소가 1개일 때 두 left,right부터
  	//차근차근 merge(정렬해서 합치기)해주면 된다.
  return merge(mergeSort(left), mergeSort(right));
}

const arr = [7, 4, 3, 2, 1, 6, 5];
const sortedArray = mergeSort(arr);
console.log(arr); //[7, 4, 3, 2, 1, 6, 5]
console.log(sortedArray); //[1, 2, 3, 4,5, 6, 7]