(JS) Merge Sort(병합 정렬) 구현하기

sorting 알고리즘 중 병합 정렬에 대해서 알아보자.

병합 정렬은 크게 두 가지 함수로 이루어져 있다.

1. function merge(left, right): 이미 소팅된 배열 left, right로 받아서 하나로 합치는 순수한 함수
2. function mergeSort(arr) : 배열을 반으로 쪼개서 merge 함수에게 left, right 인자를 넘겨주는 함수

이때, merge 함수는 순수한 함수이고, mergeSort는 재귀로 함수를 콜한다는 것을 인지해야 한다.

merge function

merge 함수는 이미 정렬된 left(배열), right(배열)을 인자로 받아서 하나로 합치는 기능이다.

const merge = function (left, right) // 정렬된 왼쪽과 오른쪽 배열을 받아서 하나로 합치는 순수한 함수
// left, rights는 이미 sorted
	const result = [];
	while (left.length !== 0 && right.length !== 0) {
      		left[0] <= right[0] ? result.push(left.shift()) : result.push(right.shift())
    	}
		return [...reulst, ...left, ...right]; // 아래 세 줄의 코드와 같은 역할 
		// if (left.length === 0) result.push(...right);
		// if (right.length === 0) result.push(...left);
		// return results;
}

mergeSort function

const mergeSort = function(array) {
  // ending condition: length === 1 인 배열이 들어올 때, 정렬이 끝난 것. 
  if (array.length === 1) return array;
  
  // 2로 나누고 내림을 해야 
  // length 가 2일 때도 안전하게 배열을 slice할 수 있다. 
  const middleIndex = Math.floor(array.length / 2);
  const left = array.slice(0, middleIndex);
  const right = array.slice(middleIndex);
  // 재귀로 계속해서 반으로 나누며 length가 1이 될때까지 쪼개고, 
  // 거꾸로 올라오면서 순수한 함수인 merge에 인자로 넣어서 다시 병합되어서 최종값을 리턴한다. 
  return merge(mergeSort(left), mergeSort(right));
}