병합 정렬 (Merge Sort)

 

[ 65, 73, 67, 98, 75, 80, 87, 30, 61, 45, 4, 36, 52, 5, 23, 68, 71, 70, 61, 21, 29, 73, 36, 90, 13,  97, 14, 71, 1, 51, 49, 3, 15, 64, 51, 87, 80, 8, 73, 84, 21, 93, 46, 87, 49, 41, 77, 40, 73, 96]

위의 gif는 실수로 아래쪽 임시 배열부분을 빠트렸다... 

그런데 배열의 데이터를 직접 지정못해줘서 아래 예시도 함께 들겠다

(모든 정렬방법의 데이터가 같은 상태)

병합 정렬이란?

재귀적으로 분할해서 정렬한후 merge하는 방법

시간복잡도

	시간 복잡도
최악	O(n log n)
평균	O(n log n)
최상	O(n log n)

공간 복잡도

전체 O(n)

 

특징

안정 정렬(Stable Sort)

분할 정복 알고리즘

임시 배열 필요

배열의 크기가 크면 이동 횟수가 많아짐

시작 복잡도가 일정하다 (데이터 분포에 영향을 덜 받음)

 

로직

재귀.

배열을 반으로 쪼갠다

배열의 길이가 1이하가 될때 까지 재귀적으로 반복한다

병합하면서 정렬한다

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

코드

function main(arr) {
  mergeSort(arr, 0, arr.length - 1);
  return arr;
}
function mergeSort(arr, left, right) {
  if (left < right) {
    let mid = parseInt((left + right) / 2);
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
  }
}
function merge(arr, left, mid, right) {
  let i = left;
  let j = mid + 1;
  let k = left;
  let sorted = [];
  while (i <= mid && j <= right) {
    if (arr[i] <= arr[j]) sorted[k++] = arr[i++];
    else sorted[k++] = arr[j++];
  }
  if (i > mid) {
    for (l = j; l <= right; l++) sorted[k++] = arr[l];
  } else {
    for (l = i; l <= mid; l++) sorted[k++] = arr[l];
  }
  for (l = left; l <= right; l++) {
    arr[l] = sorted[l];
  }
}

let arr = [
  65, 73, 67, 98, 75, 80, 87, 30, 61, 45, 4, 36, 52, 5, 23, 68, 71, 70, 61, 21, 29, 73, 36, 90, 13,
  97, 14, 71, 1, 51, 49, 3, 15, 64, 51, 87, 80, 8, 73, 84, 21, 93, 46, 87, 49, 41, 77, 40, 73, 96,
];
console.log(main(arr));

// 결과
[
   1,  3,  4,  5,  8, 13, 14, 15, 21, 21, 23,
  29, 30, 36, 36, 40, 41, 45, 46, 49, 49, 51,
  51, 52, 61, 61, 64, 65, 67, 68, 70, 71, 71,
  73, 73, 73, 73, 75, 77, 80, 80, 84, 87, 87,
  87, 90, 93, 96, 97, 98
]