[javascript] merge sort (병합정렬 자바스크립트 알고리즘) 📊

병합 정렬

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체 정렬을 하는 방법

 

 

 

 

병합 정렬은 다음 세가지 과정을 통해 이루어진다.

 

• 분할(Divide): 배열을 같은 크기의 2개의 배열로 분할한다.
• 정복(Conquer): 분할된 배열을 정렬.
• 결합(Combine): 정렬된 부분 배열을 다시 합침

 

const mergeSort = function(array) {
  if (array.length < 2) return array; 
  let pivot = Math.floor(array.length / 2); //쪼개기
  let left = array.slice(0, pivot); 
  let right = array.slice(pivot, array.length); 
  return merge(mergeSort(left), mergeSort(right)); // 재귀
}
function merge(left, right) {
  let result = [];
  while (left.length && right.length) { // ___.length가 true일 때 === 배열 안에 값이 남아있을 때
    if (left[0] <= right[0]) { 
      result.push(left.shift()); // shift() 메서드는 배열에서 첫 번째 요소를 제거하고, 제거된 요소를 반환합니다.
    } else {
      result.push(right.shift()); 
    }
  }
  while (left.length) result.push(left.shift()); 
  while (right.length) result.push(right.shift());
  return result;
};

console.log(mergeSort([5,2,4,7,6,1,3,8]));

병합정렬의 특징

 

• 안정적이다.
• O(nlog₂n)로 정렬 시간이 일정하다.
• 배열의 크기가 크면 시간이 오래걸린다.
• temp 변수가 필요하다.
• 크기가 클 경우 퀵정렬보다 효율적임