알고리즘, Sort, Merge Sort

병합 정렬(Merge Sort)은 Divide and Conquer 기법을 사용하는 효율적인 정렬 알고리즘입니다. 병합 정렬은 리스트를 반으로 나누어 각각을 재귀적으로 정렬하고, 정렬된 부분 리스트를 합쳐서 전체 리스트를 정렬합니다. 이 알고리즘은 안정적이고, 시간 복잡도가 O(n log n)으로 매우 효율적입니다.

기본 개념

병합 정렬의 기본 개념은 다음과 같습니다:

1. 분할(Divide): 리스트를 두 개의 하위 리스트로 나눕니다.
2. 정복(Conquer): 하위 리스트를 재귀적으로 병합 정렬합니다.
3. 결합(Combine): 두 개의 정렬된 하위 리스트를 하나의 정렬된 리스트로 병합합니다.

예제

다음은 자바스크립트로 구현한 병합 정렬의 예제입니다.

function merge(arr1, arr2) {
  let idx1 = 0;
  let idx2 = 0;
  let result = [];

  while (idx1 < arr1.length && idx2 < arr2.length) {
    if (arr1[idx1] < arr2[idx2]) {
      result.push(arr1[idx1]);
      idx1++;
    } else {
      result.push(arr2[idx2]);
      idx2++;
    }
  }

  // Remaining elements from arr1
  while (idx1 < arr1.length) {
    result.push(arr1[idx1]);
    idx1++;
  }

  // Remaining elements from arr2
  while (idx2 < arr2.length) {
    result.push(arr2[idx2]);
    idx2++;
  }

  return result;
}

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  let mid = Math.floor(arr.length / 2);
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

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

// [ 8, 3, 5, 4, 7, 6, 1, 2 ]
// [ 8, 3, 5, 4 ] [ 7, 6, 1, 2 ]
// [ 8, 3 ] [ 5, 4 ] [ 7, 6 ] [ 1, 2 ]
// [ 8 ] [ 3 ] [ 5 ] [ 4 ] [ 7 ] [ 6 ] [ 1 ] [ 2 ]
// [ 3, 8 ] [ 4, 5 ] [ 6, 7 ] [ 1, 2 ]
// [ 3, 4, 5, 8 ] [ 1, 2, 6, 7 ]
// [ 1, 2, 3, 4, 5, 6, 7, 8 ]

 

시간 복잡도

병합 정렬의 시간 복잡도는 다음과 같습니다:

• 최악의 경우 시간 복잡도: O(n log n)
  • 리스트를 계속해서 반으로 나누고, 각 단계에서 병합하는 데 O(n) 시간이 걸립니다.
• 평균 시간 복잡도: O(n log n)
• 최선의 경우 시간 복잡도: O(n log n)

특징

1. 안정성: 병합 정렬은 안정적입니다. 동일한 값의 요소들이 입력 순서를 유지합니다.
2. 제자리 정렬이 아님(Not In-place Sort): 병합 정렬은 추가적인 배열을 사용하여 병합 과정을 수행하기 때문에, 추가적인 메모리가 필요합니다.
3. 분할 정복 기법(Divide and Conquer): 리스트를 분할하고, 각각을 정렬한 후 병합하여 전체 리스트를 정렬합니다.

장점

1. 안정적인 정렬: 입력 데이터의 순서를 유지합니다.
2. 예측 가능한 시간 복잡도: 최선, 평균, 최악의 경우 모두 O(n log n)의 시간 복잡도를 가집니다.
3. 외부 정렬 가능: 큰 데이터를 디스크에서 정렬할 때 사용 가능합니다.

단점

1. 추가 메모리 사용: 병합 정렬은 추가적인 배열을 사용하여 병합을 수행하므로, 메모리 사용량이 늘어납니다.
2. 비교 기반 정렬: 데이터의 크기에 따라 비교 연산이 많이 필요할 수 있습니다.

결론

병합 정렬은 효율적이고 안정적인 정렬 알고리즘으로, 특히 큰 데이터 세트나 외부 정렬이 필요한 경우에 유용합니다. 그러나 추가 메모리 사용이 필요하다는 단점이 있으므로, 메모리 사용이 중요한 환경에서는 퀵 정렬(Quick Sort)과 같은 다른 정렬 알고리즘을 고려할 수 있습니다.