← 13주차 · 재귀와 분할 정복
보통분할 정복정렬

병합 정렬 직접 구현

정수 배열 nums가 주어져요. 언어의 내장 정렬을 쓰지 않고 병합 정렬로 오름차순 정렬한 새 배열을 반환해요.

병합 정렬은 세 단계예요. 배열을 반으로 나누고, 각 절반을 재귀로 정렬하고, 정렬된 두 절반을 앞에서부터 비교하며 하나로 합쳐요. 나누는 깊이가 log n이고 각 깊이에서 합치는 데 O(n)이 들어 전체가 O(n log n)이에요.

정렬 결과만 채점하지만, 연습의 핵심은 내장 정렬 없이 나누기·합치기를 직접 짜 보는 거예요.

예시

예시 1
입력
nums = [5, 2, 8, 1, 9, 3]
출력
[1, 2, 3, 5, 8, 9]
예시 2
입력
nums = [3, 1, 2]
출력
[1, 2, 3]

제한 사항

  • 0 ≤ nums.length ≤ 100,000
  • -10^9 ≤ nums[i] ≤ 10^9
  • 값이 중복될 수 있어요.
기저 조건은 길이가 1 이하면 그대로 반환하는 거예요. 아니면 가운데에서 둘로 잘라 각각 mergeSort를 부르고, 정렬된 두 배열을 인덱스 둘로 앞에서부터 비교하며 작은 값을 차례로 담아 합쳐요.
javascript
function mergeSort(nums) {
  if (nums.length <= 1) return nums;
  const mid = nums.length >> 1;
  const left = mergeSort(nums.slice(0, mid));
  const right = mergeSort(nums.slice(mid));
  const out = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    out.push(left[i] <= right[j] ? left[i++] : right[j++]);
  }
  return out.concat(left.slice(i), right.slice(j));
}
이전 문제거듭제곱 빠르게
다음 문제하노이 탑
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.