[알고리즘] 합병 정렬, 퀵 정렬, 기수 정렬

이번 글에서는 합병 정렬(Merge Sort), 퀵 정렬(Quick Sort), 기수 정렬(Radix Sort) 세 가지를 다뤄본다.
앞에서 배운 버블, 선택, 삽입 정렬보다 훨씬 빠르고, 큰 데이터셋에서도 성능이 안정적인 알고리즘들이다.

 

1. 합병 정렬 (Merge Sort)

합병 정렬은 분할 정복(Divide and Conquer) 방식으로 동작한다.
배열을 계속 반으로 나누다가 길이가 1 이하인 배열이 되면, 다시 합치면서 정렬을 완성한다.
핵심 아이디어는 정렬된 두 배열을 합치는 과정이다.

예를 들어 [8, 3, 5, 4, 7, 6, 1, 2]가 있다면:

1. 반으로 쪼갠다 → [8,3,5,4]``[7,6,1,2]
2. 또 쪼갠다 → [8,3] [5,4] [7,6] [1,2]
3. 끝까지 쪼개면 [8] [3] [5] [4] [7] [6] [1] [2]
4. 병합 → [3,8] [4,5] [6,7] [1,2]
5. 다시 병합 → [3,4,5,8] [1,2,6,7]
6. 최종 병합 → [1,2,3,4,5,6,7,8]

---

의사코드

 

헬퍼 함수: 두 정렬된 배열 합치기

함수 merge(arr1, arr2):
    결과 배열 result = []
    i, j = 0, 0
    두 배열 모두 끝까지 탐색하지 않았다면:
        arr1[i], arr2[j] 비교
        더 작은 값을 result에 추가하고 해당 포인터 이동
    남은 요소가 있다면 전부 result에 추가
    result 반환

• 합병 정렬의 핵심은 정렬된 두 배열을 하나로 합치는 과정이다.
• 먼저 result라는 빈 배열을 만든다.
• 두 배열의 시작 인덱스(i, j)를 0으로 놓고,
  두 배열 모두 아직 끝까지 다 확인하지 않았다면:
  • arr1[i]와 arr2[j]를 비교한다.
  • 더 작은 값을 result에 넣고, 그 값을 꺼낸 배열 쪽의 인덱스를 한 칸 이동시킨다.
• 둘 중 하나의 배열이 먼저 다 소비되면, 다른 배열에 남은 요소들은 이미 정렬된 상태라서 그대로 result에 붙인다.
• 마지막에 result를 반환하면, 두 배열이 정렬된 하나의 배열로 병합된다.

 

메인 함수: 합병 정렬

함수 mergeSort(arr):
    만약 배열 길이가 1 이하라면 그대로 반환
    배열을 반으로 나눔 → left, right
    왼쪽, 오른쪽에 mergeSort 재귀 호출
    merge(왼쪽, 오른쪽) 반환

• mergeSort는 배열 전체를 다루는데, 계속 쪼개서 더 이상 쪼갤 수 없을 때까지 나눈 뒤, 다시 합치는 과정에서 정렬을 완성한다.
  • 배열의 길이가 1 이하라면 그대로 반환한다. (길이가 1인 배열은 이미 정렬돼 있다고 볼 수 있음)
  • 배열을 중간에서 둘로 나눈다. (left, right)
  • 왼쪽 배열에 mergeSort를 재귀적으로 호출 → 왼쪽 부분 배열이 정렬된 상태로 반환됨.
  • 오른쪽 배열도 마찬가지로 mergeSort를 재귀적으로 호출 → 오른쪽 부분 배열이 정렬된 상태로 반환됨.
  • 이제 정렬된 왼쪽과 오른쪽 배열을 merge 함수를 이용해서 하나로 합친다.
• 최종적으로 반환되는 값은 정렬된 전체 배열이다.

---

구현 (JavaScript)

function merge(arr1, arr2) {
  let result = [];
  let i = 0, j = 0;
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      result.push(arr1[i]);
      i++;
    } else {
      result.push(arr2[j]);
      j++;
    }
  }
  while (i < arr1.length) result.push(arr1[i++]);
  while (j < arr2.length) result.push(arr2[j++]);
  return result;
}

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

---

시간 복잡도

• 최선 / 평균 / 최악: O(n log n)

1. 왜 n log n인가?

• 합병 정렬은 배열을 계속 반으로 쪼갠다.
• 길이가 n인 배열을 반씩 나누면,
• 1단계: n → 두 개의 n/2
• 2단계: 각각 n/2 → 두 개의 n/4
• 3단계: 각각 n/4 → 두 개의 n/8

따라서 log n의 시간이 소요된다.

2. 왜 n log n인가?

• 각 단계에서 merge를 통해 두 배열을 합칠 때는, 배열에 들어 있는 원소들을 모두 한 번씩 확인해야 한다.
• 즉, 배열 전체 원소 n개를 비교/복사하는 데 O(n) 시간이 든다.

전체 단계 수(log n) × 각 단계에서 필요한 작업(n)
→ O(n log n)

---

2. 퀵 정렬 (Quick Sort)

퀵 정렬 역시 분할 정복 기반이다.
배열에서 피벗(pivot)을 하나 정하고, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 모은 뒤 각각을 재귀적으로 정렬한다.

배열 [5,3,8,4,2,7,1,6]에서 피벗을 5로 잡는다고 하면:

5보다 작은 값은 왼쪽 [3,4,2,1], 큰 값은 오른쪽 [8,7,6]
피벗=5 제자리 → 정렬 중 [5] → 전체 [3,4,2,1] [5] [8,7,6]
피벗=3 → 정렬 중 [3,4,2,1] → 전체 [2,1] [3] [4] [5] [8,7,6]
피벗=8 → 정렬 중 [8,7,6] → 전체 [2,1] [3] [4] [5] [7,6] [8]
피벗=2 → 정렬 중 [2,1] → 전체 [1] [2] [3] [4] [5] [7,6] [8]
피벗=7 → 정렬 중 [7,6] → 전체 [1] [2] [3] [4] [5] [6] [7] [8]

---

의사코드

 

헬퍼 함수: 피벗 기준으로 분할

함수 pivot(arr, start, end):
    pivotValue = arr[start]
    swapIndex = start
    for i = start+1 ~ end:
        arr[i]가 pivotValue보다 작으면:
            swapIndex++
            arr[i]와 arr[swapIndex] 교환
    arr[start]와 arr[swapIndex] 교환
    swapIndex 반환

퀵 정렬의 핵심은 피벗(pivot)을 기준으로 배열을 양쪽으로 나누는 것이다.

• 우선 피벗을 배열의 맨 앞 원소로 잡는다.
• swapIndex를 피벗이 놓일 자리라고 생각하고 시작한다.
• 배열을 왼쪽에서 오른쪽으로 순회하면서 피벗보다 작은 값을 만나면 swapIndex를 하나 증가시키고, 그 자리와 교환한다.
•  swapIndex보다 왼쪽은 피벗보다 작은 값들, 오른쪽은 큰 값들이 된다.
• 마지막에 피벗을 swapIndex 자리와 교환하면 피벗은 자기 자리를 찾게 된다.

즉, pivot 함수는 배열을 피벗보다 작은 값 / 피벗보다 큰 값 두 구간으로 나누고, 피벗이 올바른 자리에 들어가도록 만든다.

 

메인 함수: 퀵 정렬

함수 quickSort(arr, left, right):
    만약 left < right:
        pivotIndex = pivot(arr, left, right)
        quickSort(arr, left, pivotIndex-1)
        quickSort(arr, pivotIndex+1, right)
    arr 반환

• 퀵 정렬은 배열을 재귀적으로 나눈다.
• 먼저 pivot 함수를 통해 피벗이 제자리를 찾고, 배열을 두 부분으로 분할한다.
• 분할된 왼쪽 구간과 오른쪽 구간에 대해 각각 다시 quickSort를 재귀적으로 호출한다.
• 배열이 더 이상 나눌 수 없을 때(구간 길이가 1 이하일 때) 재귀가 종료된다.
• 최종적으로 배열 전체가 정렬된다.

---

구현 (JavaScript)

function pivot(arr, start = 0, end = arr.length - 1) {
  let pivotValue = arr[start];
  let swapIndex = start;

  for (let i = start + 1; i <= end; i++) {
    if (arr[i] < pivotValue) {
      swapIndex++;
      [arr[i], arr[swapIndex]] = [arr[swapIndex], arr[i]];
    }
  }
  [arr[start], arr[swapIndex]] = [arr[swapIndex], arr[start]];
  return swapIndex;
}

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

---

시간 복잡도

• 평균 / 최선: O(n log n)
• 최악: O(n²) (피벗이 계속 한쪽만 분할할 경우)

1. 왜 n log n 인가?

• 퀵 정렬도 합병 정렬처럼 배열을 분할한다.
• 이상적으로는 피벗이 배열을 반씩 잘 나누면 재귀 깊이가 log n 단계가 된다.

2. 왜 n log n 인가?

• 피벗을 기준으로 원소들을 왼쪽/오른쪽으로 나누는 과정에서 배열의 모든 원소를 확인해야 한다.
• 즉, 각 단계마다 O(n) 시간이 든다.

전체 단계 log n × 각 단계 작업 n
- O(n log n)

3. 왜 최악이 O(n²)인가?

• 피벗이 배열을 균형 있게 나누지 못하고, 한쪽으로 치우치게 분할되면 (예: 이미 정렬된 배열에서 항상 첫 원소를 피벗으로 고를 경우)
  • 한쪽은 비어 있고, 한쪽만 계속 줄어드는 식으로 배열이 나뉘어진다.
  • 이 경우 재귀 깊이가 n이 되고, 각 단계에서 n만큼 비교하므로 O(n²) 이 된다.

따라서 퀵 정렬은 평균적으로는 매우 빠르지만, 피벗 선택이 안 좋으면 느려진다. (실제 구현에서는 랜덤 피벗(난수 생성) 등의 기법으로 최악 케이스를 피한다.)

---

3. 기수 정렬 (Radix* Sort)

이 때까지의 버블, 삽입, 선택, 합병, 퀵 정렬 모두 두 수를 비교하는 정렬이었다.
그러나 기수 정렬은 비교 기반이 아니라, 숫자의 자릿수를 이용한다.
가장 낮은 자릿수부터 높은 자릿수까지 차례대로 정렬하면서 최종 정렬을 완성한다.

* 'Radix(기수)'는 라틴어로 '뿌리'를 뜻하며, 숫자 시스템의 기준이 되는 수 또는 데이터를 구성하는 기본 요소를 의미한다. 10진수의 경우 0-9, 2진수의 경우 0-1의 기수를 가진다. 기수 정렬에서 각 기수들은 버킷이 된다. 

자릿수만큼 버킷에 숫자를 저장하는 것이 기수 정렬(radix sort)만의 특징.

실제 동작과정을 확인해보자.

예: [170, 45, 75, 90, 802, 24, 2, 66]

1. 1의 자리 기준 정렬 → [170,90,802,2,24,45,75,66]
2. 10의 자리 기준 정렬 → [802,2,24,45,66,170,75,90]
3. 100의 자리 기준 정렬 → [2,24,45,66,75,90,170,802]

---

의사코드

 

헬퍼 함수

함수 getDigit(num, i):
    // num의 i번째 자리수를 반환
    // 예: getDigit(732, 0) → 2 (1의 자리)
    //     getDigit(732, 1) → 3 (10의 자리)

함수 digitCount(num):
    // num의 자릿수를 반환
    // 예: digitCount(7) → 1
    //     digitCount(732) → 3

함수 mostDigits(nums):
    // 배열에서 가장 큰 자릿수를 가진 수의 자릿수 반환
    // 예: [23, 7, 105] → 3

• getDigit: 특정 자리수를 뽑아내는 함수.
• digitCount: 숫자가 몇 자리인지 알려주는 함수.
• mostDigits: 주어진 배열에서 가장 긴 숫자의 자릿수를 찾아 정렬 반복 횟수를 정한다.

이 세 함수를 사용해 각 자리수별로 제대로 버킷에 분류한다.

 

메인 함수: 기수 정렬

함수 radixSort(nums):
    maxDigit = mostDigits(nums)
    for k = 0 ~ maxDigit-1:
        숫자들을 k번째 자리 기준으로 0~9 버킷에 분배
        버킷을 다시 합쳐서 nums 업데이트
    nums 반환

1. mostDigits로 가장 큰 수의 자릿수(maxDigit)를 구한다.
2. 0번째 자리(1의 자리)부터 시작해서 차례대로 모든 자릿수를 기준으로 정렬한다.
3. 각 자리에서 숫자들을 0~9 버킷에 분류한다.
   • 예: 1의 자리 기준이면 170 → 버킷 0, 45 → 버킷 5
4. 버킷을 순서대로 합치면, 그 자릿수까지는 정렬된 상태가 된다.
5. 이 과정을 maxDigit 번 반복하면 전체 배열이 정렬된다.

기수 정렬은 비교 기반이 아니라 자릿수를 하나씩 보면서 버킷에 넣고 합치는 방식으로 정렬을 완성한다.

---

구현 (JavaScript)

function getDigit(num, i) {
  return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}

function digitCount(num) {
  if (num === 0) return 1;
  return Math.floor(Math.log10(Math.abs(num))) + 1;
}

function mostDigits(nums) {
  let max = 0;
  for (let num of nums) {
    max = Math.max(max, digitCount(num));
  }
  return max;
}

function radixSort(nums) {
  let maxDigit = mostDigits(nums);
  for (let k = 0; k < maxDigit; k++) {
    let buckets = Array.from({ length: 10 }, () => []);
    for (let num of nums) {
      let digit = getDigit(num, k);
      buckets[digit].push(num);
    }
    nums = [].concat(...buckets);
  }
  return nums;
}

---

시간 복잡도

• O(nk), 여기서 n = 데이터 개수, k = 최대 자릿수
• 공간 복잡도: O(n + k)

1. 왜 O(nk)인가?

• 기수 정렬은 1의 자리 → 10의 자리 → 100의 자리 … 이런 식으로 자릿수를 기준으로 반복한다.
• 가장 긴 수의 자릿수가 k라면 이 과정을 k번 반복한다.

2. 왜 O(nk)인가?

• 매 자리마다 모든 원소 n개를 확인해서 버킷에 넣고 다시 꺼내는 작업을 한다.
• 그래서 한 자릿수 기준 정렬은 O(n)이 든다. 

k번 반복 × 매번 n개 확인 = O(nk)

---

특징

• 비교 기반 정렬이 아님 → 숫자의 자릿수 자체를 활용한다.
• k가 작으면 (예: 자릿수가 제한된 정수 데이터) 퀵/합병보다 빠를 수 있다.
• 하지만 k가 크면 (긴 숫자 문자열 같은 경우) 비효율적일 수 있다.

 

 

이렇게 세 가지 정렬 알고리즘을 정리해봤다.
이번에 흥미로웠던 정렬은 비교 기반이 아니라 새로운 매커니즘의 기수 정렬(Radix Sort)였다.

이 때까지 다뤘던 버블, 선택, 삽입, 그리고 이 글에서 처음 나온 합병, 퀵 정렬은 비교 기반 정렬이다. 

비교 기반 정렬은 실행 방식은 조금씩 다르지만, 결국엔 두 수를 비교하여 올바르게 정렬하는 것에서 시작한다. 그런데 기수 정렬은 자릿수대로 저장소(버킷)을 생성해서 담는 것으로 정렬이 실행되는 새로운 매커니즘을 가지고 있었기에 사고의 지평이 넓어진 것 같다.