병합 정렬(Merge Sort)

병합 정렬(Merge Sort)은 배열을 반으로 나누어 각각을 재귀적으로 정렬한 후, 정렬된 두 개의 배열을 병합하여 최종적으로 정렬된 배열을 생성하는 알고리즘이다.

병합 정렬은 일반적인 방법으로 구현했을 때 분할 정복(divide and conquer) 알고리즘을 사용한다.

자바스크립트로 구현해보기

function mergeSort(arr) {
  // 배열의 길이가 1 이하이면 이미 정렬된 상태이므로 반환
  if (arr.length <= 1) {
    return arr;
  }

  // 배열을 반으로 나누기
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);

  // 재귀적으로 배열을 정렬하고 병합
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  // 왼쪽과 오른쪽 배열을 비교하며 병합
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // 남은 요소들을 결과 배열에 추가
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

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

시간 복잡도

병합 정렬의 시간 복잡도는 O(n log n)이다. 배열을 반으로 나누는 과정이 log n번 수행되며, 각 단계에서의 병합 작업은 최대 n번 수행된다. 따라서, 배열의 길이가 n인 경우에도 항상 O(n log n)의 시간 복잡도를 가지게 된다. 이로 인해 병합 정렬은 대부분의 경우 효율적이고 안정적인 정렬 알고리즘으로 사용된다.