개요

정렬 알고리즘 중 **병합정렬(Merge Sort)**과 **퀵정렬(Quick Sort)**은 모두 분할 정복(Divide and Conquer) 전략을 사용해 입력을 작고 다루기 쉬운 조각으로 나눈 뒤 병합하거나 정복하는 방식으로 동작한다.

병합정렬

• 핵심 : 배열을 반으로 계속 나누어 길이 1짜리 부분 배열들로 쪼갠 뒤, 두 정렬된 부분배열을 하나씩 병합(merge)하면서 전체를 정렬한다.
• 시간 복잡도: 모든 경우에 대해 O(n log n)이다.
• 공간 복잡도: 일반적으로 추가 배열을 사용하므로 O(n)이다.
• 안정성: 안정 정렬(stable)이다(같은 값의 상대적 순서가 보존됨).

포인트!!!!!!!

• “반으로 쪼갠다 → 각각 정렬한다 → 정렬된 두 배열을 왼쪽·오른쪽 포인터로 비교해 하나씩 꺼내 붙인다”
• 병합 과정(두 포인터 비교)이 알고리즘의 핵심이며, 병합만 제대로 이해하면 전체를 이해했다고 말할 수 있다.
• 재귀 트리 높이가 log n이고 각 레벨에서 전체 요소 n만큼 작업하므로 O(n log n)임을 직관적으로 설명한다.

JavaScript 구현 (직관적 버전)

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  
  //두 배열의 크기가 다를 때 일부 원소가 안들어갈 수도 있어서 들어간 코드
  while (i < left.length) result.push(left[i++]);
  while (j < right.length) result.push(right[j++]);
  return result;
}

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

퀵정렬 — 원리와 핵심 아이디어

• 핵심 : 배열에서 하나의 원소를 피벗(pivot)으로 선택해 피벗보다 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 분할(partition)한 뒤 재귀적으로 정렬한다.
• 평균 시간복잡도: O(n log n).
• 최악 시간복잡도: 피벗 선택이 극단적일 때 O(n^2).
• 공간복잡도: 평균적으로 O(log n) 재귀 깊이(제자리(in-place) 구현 가능).