병합정렬

병합정렬

분할 정복 알고리즘의 한 종류로서 중간값을 기준으로 두개로 배열을 나누고 각 배열의 첫번째 원소부터 비교하여 새로운 배열(정렬된 배열)에 추가하는 정렬 알고리즘. 배열을 쪼갠후 또 내부적으로 같은 과정을 반복한다(재귀적 함수 호출)

병합 정렬 예시

방법: 중간값을 기준으로 두개로 나누고
그 두개의 첫번째 요소부터 서로 비교하여 새로운 문자열에 추가
한쪽 배열이 추가되면 나머지 부분 배열을 추가

[38, 27, 43, 3, 9, 82, 10]

[38, 27, 43, 3][9, 82, 10]

[38, 27][43, 3] [9][82, 10]

[38][27] [43][3] [9][82] [10]

[27, 38][3. 43] [9, 10, 82]

[3, 27, 38, 43][9, 10. 82]

[3, 9, 10, 27, 38, 43, 92]

병합 정렬 코드

function mergeSort(arr) {
  // 배열의 크기가 1 이하이면 그대로 반환
  if (arr.length <= 1) {
    return arr;
  }

  // 중간 지점을 계산하여 두 개의 부분 배열로 분할
  const mid = Math.floor(arr.length / 2);
  const leftArr = arr.slice(0, mid);
  const rightArr = arr.slice(mid);

  // 부분 배열을 재귀적으로 정렬
  const sortedLeftArr = mergeSort(leftArr);
  const sortedRightArr = mergeSort(rightArr);

  // 정렬된 두 부분 배열을 병합
  return merge(sortedLeftArr, sortedRightArr);
}

function merge(leftArr, rightArr) {
  const result = [];

  while (leftArr.length > 0 && rightArr.length > 0) {
    if (leftArr[0] < rightArr[0]) {
      result.push(leftArr.shift());
    } else {
      result.push(rightArr.shift());
    }
  }

  // 한 쪽 부분 배열이 모두 추가되면 나머지 부분 배열을 추가
  return result.concat(leftArr, rightArr);
}

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

병합 정렬 특장점

• 장점
  - 항상 시간 복잡도가 nlogn으로 일정하다
  - 안정적인 정렬 보장
• 단점
  - 메모리 사용량이 높다

병합 정렬과 퀵정렬

일반적으로 데이터 크기가 작은 경우에는 퀵정렬을, 데이터 크기가 큰 경우에는 병합정렬을 사용하는 것이 좋음
또한, 안정적인 정렬이 필요한 경우에는 병합정렬을 사용하는 것이 좋습니다.

병합정렬과 퀵정렬 비교 Gif

• 위에 퀵정렬
• 아래가 병합정렬

병합정렬 시간복잡도에 대한 좀 더 자세한 설명 🧐

병합 정렬(merge sort)은 분할 정복(divide and conquer) 알고리즘 중 하나로, 배열을 반으로 나눈 뒤 분할된 부분 배열을 재귀적으로 정렬하고, 정렬된 부분 배열을 병합하여 최종적으로 정렬된 배열을 얻는 알고리즘입니다.

병합 정렬의 시간 복잡도는 배열의 크기를 n이라고 할 때, 주요한 단계는 배열을 반으로 나누는 분할 단계와 정렬된 부분 배열을 병합하는 병합 단계입니다. 각 단계의 시간 복잡도를 살펴보겠습니다.

1. 분할 단계: 각 단계마다 배열을 반으로 나누므로, 분할 단계의 시간 복잡도는 O(log n)입니다.
2. 병합 단계: 병합 단계에서는 두 개의 정렬된 부분 배열을 하나로 병합합니다. 이 때, 두 부분 배열의 모든 요소를 비교하여 정렬된 배열로 병합하는데, 각 단계에서 비교해야 하는 요소의 수는 n입니다.2 따라서 병합 단계의 시간 복잡도는 O(n)입니다.

🤔 병합단계가 왜 n 일까..?

첫 번째 부분 배열과 두 번째 부분 배열을 비교할 때, 각 배열에서 하나의 요소를 선택하고 비교합니다. 이 비교 연산을 수행하는 횟수는 각 부분 배열의 크기인 n/2만큼입니다. 그리고 이 비교 연산을 두 부분 배열의 모든 요소에 대해 수행해야 하므로, 총 비교해야 하는 요소의 수는 (n/2) + (n/2) = n입니다. 이렇게 각 병합 단계에서는 비교해야 하는 요소의 수가 n개인 것입니다.

분할 단계와 병합 단계가 번갈아가며 이루어지므로, 총 단계의 수는 O(log n)입니다. 각 단계에서의 시간 복잡도는 O(n)이므로, 전체 병합 정렬의 시간 복잡도는 O(n log n)입니다.