Ruby로 이해하는 병합 정렬(Merge Sort): 개념부터 구현까지

이 글은 Ruby로 다양한 정렬 알고리즘을 구현해 보는 시리즈의 세 번째 편입니다. 1편에서는 버블 정렬을, 2편에서는 선택 정렬을 다루었으니 아직 읽지 않으셨다면 함께 참고하시길 권합니다.

병합 정렬이란?

이 시리즈의 앞선 글에서 말씀드렸듯이, 데이터를 정렬하는 방법을 이해하는 것은 모든 소프트웨어 엔지니어에게 필수적인 역량입니다. 다행히 Ruby처럼 고수준 언어 대부분은 이미 효율적인 정렬 메서드를 내장하고 있습니다. 예를 들어 배열에 .sort를 호출하면 내부적으로는 퀵 정렬(quicksort)이 동작합니다. 이번 글에서는 퀵 정렬과 유사한 알고리즘인 병합 정렬(merge sort)을 알아보겠습니다. 두 알고리즘 모두 "분할 정복(divide and conquer)" 접근 방식을 활용합니다.

병합 정렬은 1945년 존 폰 노이만(John von Neumann)이 고안했습니다. 폰 노이만은 맨해튼 프로젝트, 미니맥스(mini-max) 정리, 몬테카를로 방법 등으로도 잘 알려진 저명한 컴퓨터 과학자이자 물리학자입니다.

병합 정렬의 큰 그림은 다음과 같습니다. 배열을 재귀적으로 계속 반으로 나누어 요소가 하나만 남을 때까지 분할한 뒤, 다시 요소들을 "병합(merge)"하여 최종적으로 정렬된 배열을 만듭니다. 버블 정렬 같은 단순한 알고리즘과 달리, 병합 정렬은 시각화 없이 이해하기가 꽤 까다롭습니다. 아래 다이어그램은 위키백과의 자료를 바탕으로 병합 정렬의 동작 과정을 단계별로 보여줍니다. 아직 잘 와닿지 않더라도 걱정하지 마세요. 바로 이어서 코드를 통해 하나씩 짚어보겠습니다.

Ruby로 이해하는 병합 정렬(Merge Sort): 개념부터 구현까지

왜 병합 정렬일까요? Big-O 관점에서 보기

버블 정렬과 선택 정렬은 사실상 실무에서 쓰기 어려운 수준이었지만, 병합 정렬은 빅오(Big-O) 표기법 기준으로 훨씬 좋은 성능을 보입니다. 빅오 표기법에 익숙하지 않은 분들을 위해 간단히 설명하면, 빅오는 알고리즘의 최악의 경우(worst-case) 성능을 나타내는 지표로, 서로 다른 알고리즘을 손쉽게 비교할 수 있게 해줍니다.

예를 들어 O(1)은 데이터 개수 n이 커져도 실행 시간이 일정하다는 뜻이고, O(n)은 n이 커짐에 따라 실행 시간이 선형적으로 증가한다는 의미입니다. 따라서 100개의 요소를 가진 배열을 정렬할 때 O(n) 알고리즘과 O(1) 알고리즘 중 하나를 골라야 한다면, 당연히 O(1) 알고리즘을 선택해야 합니다.

버블 정렬과 선택 정렬의 최악의 경우 성능은 O(n²)입니다. 요소 수가 늘어날수록 성능이 급격히 나빠지기 때문에 실용성이 떨어집니다. 반면 병합 정렬은 O(n log n)으로 동작하므로, 버블 정렬이나 선택 정렬만큼 효율을 크게 잃지 않습니다.

단계별 예제 살펴보기

다이어그램의 예제를 순서대로 따라가 보겠습니다. 시작 배열은 [38, 27, 43, 3, 9, 82, 10]이며, 요소가 하나만 남을 때까지 배열을 반으로 계속 나눕니다.

시작 배열을 두 부분으로 나눕니다: [38, 27, 43, 3]과 [9, 82, 10]
첫 번째 절반을 다시 나눕니다: [38, 27]과 [43, 3]
첫 번째 절반을 요소 하나 단위로 나눕니다: [38], [27], [43], [3]
38과 27을 정렬해 [27, 38]을 만들고, 43과 3을 정렬해 [3, 43]을 만듭니다.
이 둘을 합치면 [3, 27, 38, 43]이 됩니다.
이제 원래 배열의 두 번째 절반인 [9, 82, 10]으로 넘어갑니다. 반으로 나누면 [9, 82]와 [10]입니다.
[9, 82]를 [9]와 [82]로 나누고, [10]은 이미 요소가 하나뿐이므로 그대로 둡니다.
[9, 82]를 정렬해 다시 합치고 [10]을 병합하면 [9, 10, 82]가 됩니다.
마지막으로 [3, 27, 38, 43]과 [9, 10, 82]를 병합하면 [3, 9, 10, 27, 38, 43, 82], 즉 완전히 정렬된 배열이 완성됩니다.

Ruby 구현

다음은 Ruby로 작성한 병합 정렬 알고리즘입니다:

class MergeSort
  def sort(numbers)

    num_elements = numbers.length
    if num_elements <= 1
      return numbers
    end

    half_of_elements = (num_elements / 2).round

    left  = numbers.take(half_of_elements)
    right = numbers.drop(half_of_elements)

    sorted_left = sort(left)
    sorted_right = sort(right)

    merge(sorted_left, sorted_right)
  end

  def merge(left_array, right_array)
    if right_array.empty?
      return left_array
    end

    if left_array.empty?
      return right_array
    end

    smallest_number = if left_array.first <= right_array.first
      left_array.shift
    else
      right_array.shift
    end

    recursive = merge(left_array, right_array)

    [smallest_number].concat(recursive)
  end
end

sort 메서드: 배열 분할하기

먼저 코드 상단의 sort 메서드부터 살펴보겠습니다.

  def sort(numbers)

    num_elements = numbers.length
    if num_elements <= 1
      return numbers
    end

    half_of_elements = (num_elements / 2).round

    left  = numbers.take(half_of_elements)
    right = numbers.drop(half_of_elements)

    sorted_left = sort(left)
    sorted_right = sort(right)

    merge(sorted_left, sorted_right)
  end

이 부분의 목적은 주어진 배열을 요소가 하나만 남을 때까지 계속 반으로 나누는 것입니다. 실제 동작을 확인하려면 마지막 줄(merge(sorted_left, sorted_right))을 주석 처리하고 대신 sorted_left와 sorted_right를 출력해 보세요. 예제 배열을 넣어 프로그램을 실행하면 터미널에서 다음과 같은 결과를 볼 수 있습니다.

merge_sort = MergeSort.new
puts merge_sort.sort([38, 27, 43, 3, 9, 82, 10])

ruby ruby-merge-sort.rb

좋습니다! 초기 배열이 절반으로 잘 나뉜 것을 확인할 수 있습니다. 이제 merge 부분을 살펴보겠습니다.

merge 메서드: 정렬하며 병합하기

  def merge(left_array, right_array)
    if right_array.empty?
      return left_array
    end

    if left_array.empty?
      return right_array
    end

    smallest_number = if left_array.first <= right_array.first
      left_array.shift
    else
      right_array.shift
    end

    recursive = merge(left_array, right_array)

    [smallest_number].concat(recursive)
  end

먼저 두 하위 배열 중 하나가 비어 있는지 검사합니다. 비어 있다면 나머지 배열을 그대로 반환하면 됩니다. 둘 다 비어 있지 않다면 각 배열의 첫 번째 요소 값을 비교한 뒤, 비교된 값을 shift로 제거합니다. 이렇게 하는 이유는 무한 루프에 빠지는 것을 방지하기 위함입니다. 이후 원래 배열에 대해 재귀 호출을 계속 수행하다가, 마지막에는 두 배열이 깔끔하게 정렬된 상태로 연결됩니다.

재귀(recursion) 조금 더 알아보기

코드에서 뭔가 낯설게 느껴지는 부분이 있다면 아마 이 줄일 겁니다: recursive = merge(left_array, right_array). merge 메서드 안에서 그 메서드 자신을 다시 호출하고 있습니다. 놀랍죠? 이것이 바로 재귀(recursion)입니다. 함수가 특정 조건이 충족될 때까지 자기 자신을 한 번 이상 호출하는 기법을 말합니다. 우리 코드에서는 왼쪽 또는 오른쪽 배열이 빌 때까지 merge가 계속 호출됩니다. 재귀에 대해 더 알아보고 싶다면, Ruby와 재귀를 활용해 피보나치 수열 함수를 작성하는 예제를 찾아보시길 추천합니다.

마무리

병합 정렬에 대해 배워 보았습니다! 병합 정렬이 어떻게 동작하는지 큰 그림을 이해하고, 버블 정렬이나 선택 정렬보다 왜 더 효율적인 선택인지 아는 것은 코딩 면접이나 실무에서 분명 도움이 될 것입니다. 병합 정렬에는 여러 변형(variant)도 존재하니, 관심이 있다면 위키백과에서 더 자세히 읽어보세요. 그럼 다음 글에서 만나요. 즐거운 정렬 되세요!