mergesort [ 합병정렬 ] javascript 구현

mergesort [ 합병정렬 ] 로직 유명하죠. 자바스크립트로는 구현한적이 없어서 구현해봤습니다.

로직

배열을 절반으로 나누어 각각 정렬한 후, 합친다.

그런데 자바스크립트 특성상 배열을 복사하는 방법이 편해서 다음과 같이 구현하였습니다.

유명한 로직이라 자세한 설명보다 visuAlgo를 보면서 로직을 이해하면 됩니다.

code

//Node.js에서 콘솔로 입력받기
var readline = require("readline");

var rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

rl.question("", function(answer) {
  const arr = answer.split(" ");
  console.log(mergeSort(arr));
  rl.close();
});

function mergeSort(numbers) {
  if (!numbers || numbers.length === 1) {
    return numbers;
  }

  const middle = Math.floor(numbers.length / 2);
  const left = numbers.slice(0, middle);
  const right = numbers.slice(middle, numbers.length);
  const mergeLeft = mergeSort(left);
  const mergeRight = mergeSort(right);

  let leftIdx = 0,
    rightIdx = 0;

  const sortedNumber = [];

  while (leftIdx < mergeLeft.length && rightIdx < mergeRight.length) {
    if (mergeLeft[leftIdx] < mergeRight[rightIdx]) {
      sortedNumber.push(mergeLeft[leftIdx++]);
    } else {
      sortedNumber.push(mergeRight[rightIdx++]);
    }
  }

  if (leftIdx === mergeLeft.length) {
    while (rightIdx < mergeRight.length) {
      sortedNumber.push(mergeRight[rightIdx++]);
    }
  } else {
    while (leftIdx < mergeLeft.length) {
      sortedNumber.push(mergeLeft[leftIdx++]);
    }
  }

  return sortedNumber;
}

Array.prototype.slice() : 새로운배열 [시작인덱스~마지막인덱스-1] :slice(시작인덱스, 마지막인덱스) 원본 배열은 그대로

Array.prototype.splice() : 제거한 요소를 담은 배열 : splice(시작인덱스, 제거할 개수), 원본배열도 수정됌

참고:
slice, splice