merge Sort ( 합병정렬 )

합병정렬이란?

위의 그림과 같은 방식으로 작동해 배열을 정렬시켜주는 알고리즘입니다.
합병 정렬은 비교 기반 정렬 알고리즘으로 시간복잡도는 O(NlogN)입니다.

시간복잡도

• 최악 시간복잡도: O(nlogn)
• 평균 시간복잡도: O(nlogn)
• 최선 시간복잡도: O(nlogn)

 

합병정렬 javascript로 구현하기

병합정렬은 크게 두 가지 함수로 이루어져 있다.

1. function merge(left, right) : 이미 소팅된 배열 left, right 받아서 하나로 합치는 순수한 함수
2. function mergeSort(arr) : 배열을 반으로 쪼개서 merge 함수에게 left, right 인자를 넘겨주는 함수

이 때, merge함수는 순수한 함수이고, mergeSort는 재귀로 함수를 콜한다는 것을 인지해야 한다.

 

merge function

merge 함수는 이미 정렬 된 left(배열), right(배열)를 인자로 받아서 하나로 합치는 기능

results array 선언
while left, right 모두 element 남아 있을 때까지
    left[0] <= right[0] left의 맨 앞에 것 빼서 results 에 푸쉬
    left[0] > right[0] right의 맨 앞에 것 빼서 results 에 푸쉬

return [...results, ...left, ...right] 남은 것 다 배열에 넣어주기

mergeSort function

mergeSort 는 반으로 쪼개서 merge 에게 인자를 넘겨주는 기능

이 함수의 recursive call 종료 조건은 legnth 가 1일 때, 더 이상 쪼갤 수 없게 된다. => 정렬된 배열인 셈이다.
length >=2 이면 계속해서 반으로 쪼갠다

return merge( mergeSort(left), mergeSort(right) );
// legnth 1이 될 때 까지 쪼개다가 length === 1인 배열을 만나면
// 그제서야 merge함수가 실행된다. legnth 가 1일때 가장 아랫단계에서 sorted 된 것이므로.. 쭉쭉 스택콜을 타고 올라온다.

이용되는 2가지 함수를 봤으니 코드를 보고 이해해봅시다!

unction merge(left, right) {
  const sortedArr = [];
  while (left.length && right.length) {
    //left[0]이 더작을 경우 같을때는 누가 먼저 들어가도 상관X
    if (left[0] <= right[0]) {
      sortedArr.push(left.shift());
    } else {
      sortedArr.push(right.shift());
    }
  }
  //left,right 둘 중 하나는 요소가 남아있기 때문에 sortedArr 뒤에 붙여서 출력
  //비어있으면 spread Syntax에도 아무것도 없기 때문에 그냥 다 붙여준다.
  return [...sortedArr, ...left, ...right];
}

function mergeSort(arr) {
  if (arr.length === 1) return arr;
  const boundary = Math.ceil(arr.length / 2);
  //slice로 해주기 때문에 원본 arr은 손상 없다.
  const left = arr.slice(0, boundary);
  const right = arr.slice(boundary);
    //요소가 1개 일 때까지 재귀를 실행해 요소가 1개일 때 두 left,right부터
  	//차근차근 merge(정렬해서 합치기)해주면 된다.
  return merge(mergeSort(left), mergeSort(right));
}

const arr = [7, 4, 3, 2, 1, 6, 5];
const sortedArray = mergeSort(arr);
console.log(arr); //[7, 4, 3, 2, 1, 6, 5]
console.log(sortedArray); //[1, 2, 3, 4,5, 6, 7]