자바스크립트 정렬 알고리즘 5 : Merge Sort

*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.

*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)

---

앞서 살펴본 Bubble Sort, Selection Sort, Insertion Sort는 시간복잡도가 O(n^2)가 되기 때문에 무척이나 비효율적인 정렬 알고리즘이었다.(특정 조건에서 Insertion Sort는 제외. 자세한 것은 이 글에서 확인할 수 있다.)

Merge Sort는 Divide and Conquer 및 recursion을 활용하는 로직이며, 따라서 O(n^2)에서 더 개선된 O(n log n)의 시간복잡도이다. 

 

Merge Sort는 기본적으로 모든 element가 한 번 이상씩 비교가 되기는 하기 때문에 O(n)을 기록하게 되지만, 모든 element가 매 번 다른 모든 element와 비교되지 않고, 구역을 나눈 후, 그 안에서만 비교를 하기 때문에 O(log n)도 가지게 된다.

 

Merge Sort의 또 다른 특징은 Stable하다는 점이다. 만약 정렬해야 하는 자료에 value가 동일한 element가 존재할 경우, 원본 배열의 순서를 변경하지 않게 된다. 특정 상황, 특정 자료구조형에 따라서 이 특성을 매우 중요할 수 있다.

 

공간복잡도가 O(n)에 해당되기는 하나, 굉장히 효율적인 알고리즘이기 때문에 자주 사용된다.

 

☞ Merge Sort 로직

 

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function mergeSort (array) {
  if (array.length === 1) {
    return array
  }
  // Split Array in into right and left
  const length = array.length;
  const middle = Math.floor(length / 2)
  const left = array.slice(0, middle) 
  const right = array.slice(middle)
  // console.log('left:', left);
  // console.log('right:', right);

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

function merge(left, right){
  const 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++
    }
  }  
  // console.log(left, right)
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}


const answer = mergeSort(numbers);
console.log(answer);