알고리즘 - 머지 정렬(Merge sort) / 머지 정렬 구현

머지 정렬?

---

머지는 두 개의 정렬된 배열을 하나의 큰 정렬된 배열로 합치는 작업을 의미한다. 배열을 정렬할 때 배열을 반으로 나누어 각각의 절반에 대해서 재귀적으로 정렬을 수행하고 정렬된 결과를 다시 재귀적으로 병합하는 것을 머지 정렬이라고 한다.

 

📌 하향식 머지 정렬

하향식 머지 정렬은 배열이 주어졌을 때, 배열을 더 이상 나눌 수 없을 때까지 나누고 배열이 더 이상 나누어질 수 없을 때 머지 정렬을 실행한다.

 

📌 실행 시간 개선 방법

1. 머지 정렬은 재귀적으로 동작하기 때문에 나누어진 배열의 크기가 작다면 삽입 정렬 알고리즘을 사용하는 게 좋다.
2. 배열이 이미 정렬되었는지 확인하고 이미 정렬된 상태로 입력되는 배열에 대한 중복된 정렬을 생략하면 이미 정렬된 부분 배열에 대한 실행 시간이 선형으로 줄어든다.
3. 원본 배열과 임시 배열을 번갈아 가며 사용하면 복사 작업을 줄여 성능을 향상시킬 수 있다. 즉, 병합 정렬의 각 단계에서 원본 배열과 임시 배열을 서로 바꿔가며 사용하여 복사를 줄일 수 있다.

 

📌 상향식 머지 정렬

상향식 머지 정렬은 작은 부분 배열들을 한 번의 순회로 병합할 수 있도록 병합하는 순서를 조정하는 것이다. 그 다음 순회에서 더 커진 부분 배열들을 짝지어서 병합한다. 이러한 방법으로 부분 배열의 크기를 늘려가면서 머지 정렬을 수행한다.

 

📌 연결리스트로 정렬할 데이터 관리하기

정렬되어야 할 부분 리스트로 크기 1인 리스트가 있을 때 병합 단계를 한 번 지나면 크기 2인 정렬된 부분 리스트가 만들어진다. 단계를 한 번 더 지나면 크기 4인 정렬된 부분 리스트가 만들어진다. 이렇게 전체 배열이 정렬될 때까지 진행하는 방법이 있다. 이렇게 하면 새로운 링크를 생성하거나 임시 리스트에 복제할 필요 없이 기존 리스트의 연결 상태만 바꾸어서 정렬 상태로 만들 수 있다.

 

📌 머지 정렬의 장단점

머지 정렬의 장점은 크기 N인 배열을 정렬하는 시간이 NlogN에 비례한다는 것이다. 대신 N에 비례하는 추가적인 메모리 공간을 소요하는 것이 단점이기도 하다.

 

📌 머지 정렬의 효율성

머지 정렬의 효율성은 O(NlogN)이다.

	최선의 경우	평균의 경우	최악의 경우	추가 공간
머지 정렬	O(NlogN)	O(NlogN)	O(NlogN)	N

 

Ex.

 

const merge = (array, start, mid, end) => {
  let left = start,
      right = mid + 1;

  const copyArray = [...array];

  for(let i = start; i <= end; i++){
    if(left > mid){ // 오른쪽 요소로 이동
      array[i] = copyArray[right];
      right++;
    }else if(right > end){ // 왼쪽 요소로 이동
      array[i] = copyArray[left];
      left++;
    }else if(copyArray[left] < copyArray[right]){ // 왼쪽과 오른쪽 요소 중 왼쪽 값이 더 작을 경우
      array[i] = copyArray[left];
      left++;
    }else{
      array[i] = copyArray[right]; // 왼쪽과 오른쪽 요소 중 오른쪽 값이 더 작을 경우
      right++;
    }
  }
}

const mergeSort = (array, start = 0, end = array.length - 1) => {
  if(start >= end) return; // 리스트가 나뉘어지지 않을 만큼 반복 한다.

  const mid = Math.floor((start + end) / 2); // 리스트를 반으로 나눈 길이.

  mergeSort(array, start, mid); // 분할한 배열 왼쪽 리스트 정렬
  mergeSort(array, mid + 1, end); // 분할한 배열 오른쪽 리스트 정렬
  merge(array, start, mid, end);
};