Merge Sort(병합정렬)

병합정렬은 한 배열을 반복적으로 반으로 나누어 정렬하고 다시 합치는 방식으로 이루어지는 정렬 알고리즘이다. 병합정렬은 보통 두 가지 함수로 이루어져 있는데
해당 함수는 다음과 같다.

1. 이미 나누어 정렬한 배열을 하나로 합치는 함수

function merge(left, right){
  const result = [];
  while(left.length > 0 && right.length > 0){
    if(left[0] <= right[0]) {
      result.push(left.shift());
    }
    else if(left[0] > right[0]) {
      result.push(right.shift());
    }
  }
  return [...result, ...left, ... right];
}

해당 함수는 반으로 나누어 전달받은 인자를 비교해서 정렬하게 된다.

2. 배열을 반으로 나누어, merge 함수에게 left, right 인자를 넘겨주는 함수

function mergeSort(arr) {
  if(arr.length === 1) return arr;
  const middleIdx = Math.floor(arr.length / 2);
  const left = arr.slice(0, middleIdx);
  const right = arr.slice(middleIdx);
  return merge(mergeSort(left), mergeSort(right));

해당 함수는 배열의 길이가 1이 될때까지(요소가 1개만 남을 때까지)재귀적 반복과정을 거쳐서 merge함수에 left와 right로 전달되게 된다. 이후 왼쪽 배열과 오른쪽 배열을 비교해서 합치는 과정을 반복하게 되고 결과적으로는, 정렬된 배열을 만들 수 있다.