MergeSort.js

MergeSort.js

function mergeSort(unsortedArr) {
  // Base Case
  if (unsortedArr.length <= 1) {
    return unsortedArr
  }
  
  const mid = Math.floor(unsortedArr.length / 2); 
  
  const left = unsortedArr.slice(0, mid);
  const right = unsortedArr.slice(mid); 

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

// 배열을 비교하고, 연결된 결과를 리턴한다.
function merge(left, right) {
  let result = [],
      leftIdx = 0,
      rightIdx = 0;

  // left items와 right items 비교
  while(leftIdx < left.length && rightIdx < right.length) {
    if (left[leftIdx] < right[rightIdx]) {
      result.push(left[leftIdx]);
      leftIdx++;
    } else {
      result.push(right[rightIdx]);
      rightIdx++;
    }
  }

  return [...result, ...left.slice(leftIdx), ...right.slice(rightIdx)];
}

const list = [2, 5, 1, 3, 7, 2, 3, 8, 6, 3];
console.log(mergeSort(list)); // [ 1, 2, 2, 3, 3, 3, 5, 6, 7, 8 ]