MergeSort(병합정렬) 구현하기

merge sort

말그래도 배열을 병합(merge)하여 정렬하는 알고리즘이다. 병합이라는 말과 같이 배열을 재귀적으로 쪼갤 수 없는 단위 즉, 요소가 1개가 남을 때까지 쪼갠 후 정렬하고 쪼개진 요소들을 병합한다.

출처: 위키백과 - Swfung8 자작

병합정렬을 위해선 두가지의 함수가 필요하다.

1. merge 함수

• 이 함수는 인자로 정렬된 두개의 배열을 받아 하나의 배열로 합쳐주는 순수 함수(pure function)이다.

2. mergeSort 함수

• 이 함수는 인자로 정렬할 배열을 받아 두개의 배열로 쪼갠 뒤 merge함수에게 인자로 두개의 배열을 넘겨주는 함수이다. 이 함수는 재귀적 함수를 콜한다.

수도 코드

merge 함수

// 입력받은 배열을 합칠 result 배열 선언

// 입력받은 배열1, 배열2의 요소가 없을 때까지
   // 배열1과 배열2의 첫번째요소 중 작은 녀석들을 result에 담아준다.

// result와 배열1, 배열2의 남은 요소들을 배열로 다시 묶어 리턴한다.

mergeSort 함수

// 재귀적 호출 시 종료 조건으로 입력 받은 배열의 길이가 1개일 경우 즉, 이미 정렬된 경우 해당 배열을 리턴한다.

// 입력받은 배열을 두개로 쪼갠다.
// 쪼개기 위해 mid변수를 선언하고 입력받은 배열의 길이 / 2 값을 내림하여 담아둔다.
// 쪼갠 뒤 왼쪽 배열을 담을 left 배열을 선언하고 담는다.
// 오른쪽 배열 역시 담아둔다. 

// 재귀함수를 콜하여 left배열과 right배열을 담아 merge함수의 인자로 넣어준 뒤, 그 값을 리턴한다. 

구현

const merge = (left, right) => {
  const result = [];
  
  while(left.length !== 0 && right.length !== 0) {
    left[0] <= right[0] ? result.push(left[0]) : result.push(right[0]);
  }
  
  return [...result, ...left, ...right];
}


const mergeSort = (arr) => {
  // 재귀 종료 조건
  if(arr.length < 2) return arr;
  
  const midIdx = Math.floor(arr.length / 2);
  const leftArr = arr.slice(0, midIdx);
  const rightArr = arr.slice(midIdx);
  
  return merge(mergeSort(left), mergeSort(right));
}

장점

• 시간복잡도 상 O(NlogN)으로 일정한 속도로 정렬된다.

단점

• 추가적인 메모리 공간이 필요하다.