[바미] Sorting algorithm - Merge sort 알고리즘 구현하기

function mergeSort(array) {
  if (array.length <= 1) {
    return array;
  }

  const middle = Math.floor(array.length / 2);
  const left = array.slice(0, middle);
  const right = array.slice(middle);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

---

코드 설명

function mergeSort(array) {
  if (array.length <= 1) {
    return array;
  }

mergeSort 함수는 입력 배열의 길이가 1 이하인 경우에는 그대로 배열을 반환해주는데 이미 정렬된 배열을 다시 정렬하지 않기 위해 만들어진 함수입니다.

 

  const middle = Math.floor(array.length / 2);
  const left = array.slice(0, middle);
  const right = array.slice(middle);

배열의 길이가 1 이상인 경우, 배열을 절반으로 쪼개 left와 right 두 개의 배열을 만들어 줍니다.

 

  return merge(mergeSort(left), mergeSort(right));
}

쪼개어진 두 개의 배열을 각각 mergeSort 함수를 호출하여 다시 정렬하게 되는데 결과는 merge 함수에서 합쳐지며, 최종적으로 mergeSort 함수에서 반환되게 됩니다.

 

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

merge 함수에서는 결과 배열 result와 left와 right 배열의 인덱스를 각각 관리하는 leftIndex와 rightIndex를 초기화 시켜주고

 

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

left와 right 두 개의 배열 중 하나가 끝날 때까지, 비교하여 작은 값을 result 배열에 넣어 줍니다.

한쪽의 배열이 끝나면 다른 한쪽의 배열을 남은 것 전체를 그대로 result 배열에 넣어 줍니다.

 

return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

위 과정이 끝나면 result 배열에 left와 right 두 개의 배열이 정렬된 형태로 합쳐지게 되고, 이를 반환하면 mergeSort 함수에서 결과를 얻을 수 있게 됩니다.