[알고리즘] 합병정렬(Merge Sort)

const merge = (leftArray, rightArray) => {
  const result = [];
  let leftPoint = 0;
  let rightPoint = 0;

  while (leftPoint < leftArray.length && rightPoint < rightArray.length) {
    if (leftArray[leftPoint] < rightArray[rightPoint]) {
      result.push(leftArray[leftPoint]);
      leftPoint++; // 왼쪽 array값이 더 작을 경우 result에 값을 push
    }
    if (leftArray[leftPoint] > rightArray[rightPoint]) {
      result.push(rightArray[rightPoint]);
      rightPoint++; // 오른쪽 array값이 더 작을 경우 result에 값을 push
    }
  }

  while (leftPoint < leftArray[leftPoint]) {
    result.push(leftArray[leftPoint]);
    leftPoint++; // array의 나머지 값을 result에 push
  }
  while (rightPoint < rightArray[rightPoint]) {
    result.push(rightArray[rightPoint]);
    rightPoint++; // array의 나머지 값을 result에 push
  }

  return result;
};

const mergeSort = (array) => {
  if (array.length <= 1) return array;
  let mid = Math.floor(array.length / 2);

  let left = mergeSort(array.slice(0, mid)); // 재귀로 왼쪽 오른쪽으로 절반씩 나누기
  let right = mergeSort(array.slice(mid)); // 재귀로 왼쪽 오른쪽으로 절반씩 나누기

  const result = merge(left, right); // merge하기

  return result;
};

시간복잡도	O(N)
Best	O(nlogn)
Average	O(nlogn)
Worst	O(nlogn)