병합 정렬(Merge Sort)

합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현

분할 정복이란?

큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식

빠른 정렬로 분류되며, 퀵소트와 함께 많이 언급되는 정렬 방식이다.

퀵소트와는 반대로 안정 정렬에 속함

시간복잡도

평균최선최악

Θ(nlogn)

Ω(nlogn)

O(nlogn)

요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식으로, 쪼개는 방식은 퀵정렬과 유사

• mergeSort

function mergeSort(array, left, right) {
  if (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    mergeSort(array, left, mid);
    mergeSort(array, mid + 1, right);
    merge(array, left, mid, right);
  }
}

정렬 로직에 있어서 merge() 메소드가 핵심

퀵소트와의 차이점

퀵정렬 : 우선 피벗을 통해 정렬(partition) → 영역을 쪼갬(quickSort)

합병정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) → 정렬(merge)

• merge()

function merge(array, left, mid, right) {
  const leftSize = mid - left + 1;
  const rightSize = right - mid;
  const leftArray = new Array(leftSize);
  const rightArray = new Array(rightSize);
  // 임시 배열로 데이터 복사
  for (let i = 0; i < leftSize; i++) {
    leftArray[i] = array[left + i];
  }
  for (let j = 0; j < rightSize; j++) {
    rightArray[j] = array[mid + 1 + j];
  }
  let i = 0; // 첫 번째 하위 배열의 초기 인덱스
  let j = 0; // 두 번째 하위 배열의 초기 인덱스
  let k = left; // 병합된 하위 배열의 초기 인덱스
  // 임시 배열을 원본 배열로 병합
  while (i < leftSize && j < rightSize) {
    if (leftArray[i] <= rightArray[j]) {
      array[k] = leftArray[i];
      i++;
    } else {
      array[k] = rightArray[j];
      j++;
    }
    k++;
  }
  // 남은 원소가 있는 경우, 첫 번째 하위 배열의 남은 원소 복사
  while (i < leftSize) {
    array[k] = leftArray[i];
    i++;
    k++;
  }
  // 남은 원소가 있는 경우, 두 번째 하위 배열의 남은 원소 복사
  while (j < rightSize) {
    array[k] = rightArray[j];
    j++;
    k++;
  }
}

이미 합병의 대상이 되는 두 영역이 각 영역에 대해서 정렬이 되어있기 때문에 단순히 두 배열을 순차적으로 비교하면서 정렬할 수가 있다.

★★★합병정렬은 순차적인 비교로 정렬을 진행하므로, LinkedList의 정렬이 필요할 때 사용하면 효율적이다.★★★

LinkedList를 퀵정렬을 사용해 정렬하면?

성능이 좋지 않음

퀵정렬은, 순차 접근이 아닌 임의 접근이기 때문

LinkedList는 삽입, 삭제 연산에서 유용하지만 접근 연산에서는 비효율적임

따라서 임의로 접근하는 퀵소트를 활용하면 오버헤드 발생이 증가하게 됨

배열은 인덱스를 이용해서 접근이 가능하지만, LinkedList는 Head부터 탐색해야 함

배열[O(1)] vs LinkedList[O(n)]

function solve() {
  let array = [230, 10, 60, 550, 40, 220, 20];
  mergeSort(array, 0, array.length - 1);
  for (let v of array) {
    console.log(v);
  }
}

function mergeSort(array, left, right) {
  if (left < right) {
    let mid = Math.floor((left + right) / 2);

    mergeSort(array, left, mid);
    mergeSort(array, mid + 1, right);
    merge(array, left, mid, right);
  }
}

function merge(array, left, mid, right) {
  let L = array.slice(left, mid + 1);
  let R = array.slice(mid + 1, right + 1);

  let i = 0, j = 0, k = left;
  let ll = L.length, rl = R.length;

  while (i < ll && j < rl) {
    if (L[i] <= R[j]) {
      array[k] = L[i++];
    } else {
      array[k] = R[j++];
    }
    k++;
  }
  while (i < ll) {
    array[k++] = L[i++];
  }
  while (j < rl) {
    array[k++] = R[j++];
  }
}