합병 정렬(merge sort)

합병 정렬이란?

분할 정복 방식을 사용해 데이터를 분할하고, 분할한 배열을 정렬하며 합치는 알고리즘

분할 정복법(Divide and Conquer)?

• 주어진 문제를 작은 사례로 나누고(Divide), 각각의 문제들을 해결해서 정복(Conquer)하는 방법이다. 이때 작은 사례가 문제를 해결할 만큼 충분히 작지 않으면 재귀를 사용하여 다시 나누고 정복하는 과정을 반복한다.
• 정복이라는 단어가 사용되는 게 특이해서 검색해보았는데 나폴레옹이 아우스터리츠 전투에서 오스트리아와 러시아 연합군을 물리치기 위해 중앙으로 들어가 적을 둘로 갈라놓고 개별적으로 싸워 이긴 사례에서 따왔다고 한다..

합병 정렬의 과정

1. 분할 : 입력 받은 배열을 반으로 나눈다.
2. 정복 : 나누어진 배열이 충분히 작아질 때까지 재귀 호출하여 나누고, 정렬한다.
3. 결합 : 정렬된 배열들을 하나의 배열에 병합한다.

합병 정렬의 특징

• 적은 시간 복잡도를 가진다.
• 동일한 값에 대해 기존의 순서가 유지되는 안정 정렬이다.
• 추가적인 리스트를 필요로 하므로 메모리를 차지한다.

합병 정렬의 시간 복잡도

O(nlogn)의 시간 복잡도를 가지고 있다.

의사코드

function merge(left,right) {
  
  빈 배열을 선언한다
  
  left, right에 값이 존재하는 동안 반복문을 돌린다
  만약 left의 첫 번째 인덱스와 right의 첫 번째 인덱스를 비교해서
  작은 수를 빈 배열에 넣는다
  
  만약 left나 right 중 하나에만 값이 존재할 경우
  배열의 마지막에 그 값을 넣어준다
  
  배열을 리턴해준다(이 값이 mergeSort의 리턴값이 될 것이다)
}

function mergeSort(arr) {
  
  //base case 
  만약 배열의 길이가 1보다 작으면 바로 리턴한다.
    
  //recursive case
  중간값을 구한다(나누어떨어지지 않으면 내림) Math.floor(arr.length/2)
  중간값을 기준으로 left와 right로 나눈다.
  left와 right를 각각 mergeSort로 재귀호출한다. 만약 배열의 길이가 1보다 작으면  리턴될 것이다
  리턴 값을 merge 함수로 병합한다.
}

코드

function merge(left, right) {
  const sorted = [];
  while(left.length && right.length){
   if(left[0] < right[0]){
    sorted.push(left.shift()); //left[0]이 작을 때 
   } else {
    sorted.push(right.shift()); //right[0]이 작을 때
   }
 }
  return [...sorted,...left,...right];
  
}

function mergeSort(arr) {
  //base case 
  if(arr.length <= 1) return arr;
  
  //recursive case
  const mid = Math.floor(arr.length /2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  
  return merge(mergeSort(left),mergeSort(right));
}

left나 right 중에 남은 숫자는 마지막에 붙는다.