[Algorithm] 합병 정렬(merge sort) 정리

합병 정렬(merge sort) 이란?

합병 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다.

📖 안정 정렬 이란?

안정 정렬 알고리즘은 반복되는 요소를 입력 때와 동일한 순서로 정렬시킨다. (참고)

📖 분할 정복 알고리즘(Divide and conquer alogorithm) 이란?

그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 알고리즘이다.
분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.

---

합병 정렬(merge sort) 과정

합병 정렬 4단계
분할(Divide) → 정복(Conquer) → 결합(Combine)→ 복사(Copy)

1.  분할(Divde)
   • 정렬되지 않은 리스트를 절반으로 잘라 리스트를 두 부분으로 나눈다.
2. 정복(Conquer)
   • 부분 배열을 정렬한다.
   • 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복을 반복한다.
3. 결합(Combine)
   • 정렬된 부분 배열들을 하나의 배열에 합병한다.
   • 이때 정렬 결과가 임시 배열에 저장된다.
4. 복사(Copy)
   • 임시 배열에 저장된 결과를 원래 배열에 복사한다.

📖 주의 깊게 볼 점

- 합병 정렬은 추가적인 리스트가 필요하다.
- 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.
- 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계이다.

---

합병 정렬(merge sort) 예제

• 배열에 7, 3, 2, 16, 24, 4, 11, 9가 저장되어 있고, 이를 오름차순으로 정렬해야 한다.
• 2개의 정렬된 리스트를 합병(merge)하는 과정
  1. 2개의 리스트의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트(tmpArray)에 넣는다.
  2. 두 개의 리스트 중에서 하나가 끝날 때까지 이 과정을 되풀이한다.
  3. 나머지 리스트의 값들을 전부 새로운 리스트(tmpArray)에 넣는다.
  4. 새로운 리스트(tmpArray)를 원래의 리스트(array)로 옮긴다.

---

합병 정렬(merge sort) JavaScript 코드

const merge = (start, mid, end) => {
  // LIndex: 정렬된 왼쪽 배열에 대한 인덱스
  // RIndex: 정렬된 오른쪽 배열에 대한 인덱스
  // tmpIndex: 정렬될 배열에 대한 인덱스
  let LIndex = start;
  let RIndex = mid + 1;
  let tmpIndex = start;
  
  // 분할 정렬된 list의 합병
  while (LIndex <= mid && RIndex <= end) {
    if (array[LIndex] <= array[RIndex]) {
      tmpArray[tmpIndex++] = input[LIndex++];
    } else {
      tmpArray[tmpIndex++] = input[RIndex++];
    }
  }
  
  // 남아 있는 값들 임시 배열에 일괄 복사
  while (LIndex <= mid) {
    tmpArray[tmpIndex++] = input[LIndex++];
  }
  while (RIndex <= end) {
    tmpArray[tmpIndex++] = input[RIndex++];
  }
  
  // 임시 배열의 값들을 원본 배열에 복사
  for (let i = start; i <= end; i++) {
    array[i] = tmpArray[i];
  }
};

const mergeSort = (start, end) => {
  if (start < end) {
    const mid = Math.floor((start + end) / 2); // 분할(Divide)
    mergeSort(start, mid);	// 왼쪽 배열 정복(Conquer)
    mergeSort(mid + 1, end); // 오른쪽 배열 정복(Conquer)
    merge(start, mid, end); // 정렬된 2개의 부분 배열을 합병(Merge)
  }
};

const array = [7, 3, 2, 16, 24, 4, 11, 9];
const tmpArray = [];
mergeSort(0, N - 1);

 

---

References

• 합병 정렬 - 위키백과
• https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html