Scala로 만들어본 Merge Sort

머지 소트(병합 정렬) 역시 강력하고 쉬운 알고리즘이다.

절반으로 계속 나누어 나가다가 더 이상 나눌 수 없어지면 다시 합치는 알고리즘이다. 

단지 합칠 때 작은 값과 큰 값의 순서를 확인하면서 합쳐나가는 것이 포인트다.

퀵 소트와 마찬가지로 절반으로 나누어 재귀호출하기 때문에 로그단위의 복잡도를 가진다.

하지만 퀵 소트와는 다르게 이미 정렬된 값은 순서 그대로 합쳐져 stable한 결과를 가진다.

위키백과의 그림을 참고해 설명하자면

이렇게 두 단계로 나눌 수 있다. 

노란 색으로 표시한 두 배열을 합치는 방법을 좀 더 자세히 보면

이런 순서가 된다.

합칠 값 두개를 비교한 후 더 작은 값을 새로 만들 배열에 넣고, 나머지 값을 재귀호출 하는 것이다.

스칼라 코드로 구현하면 아래처럼 될 것이다.

def mergeSort[A](lst: List[A])(implicit ord: A => Ordered[A]): List[A] = {
  def merge(lLst: List[A], rLst: List[A]): List[A] = (lLst, rLst) match {
    case (Nil, right) => right
    case (left, Nil) => left
    case (lh::lt, rh::rt) =>
      if(lh > rh) rh::merge(lLst, rt)
      else lh::merge(lt, rLst)
  }

  if(lst.isEmpty || lst.length == 1) lst
  else {
      val mid = lst.length / 2
      val (lLst, rLst) = lst.splitAt(mid)
      merge(mergeSort(lLst), mergeSort(rLst))
  }
}

두개의 리스트를 입력받아 합쳐 리턴하는 merge 함수와 그 과정을 재귀호출하는 mergeSort 함수로 구성했다.

포인트가 되는 merge 함수에서는 

어느 한 쪽이 비어있으면 비어있지 않은 쪽을 리턴하고

양 쪽 다 비어있지 않으면 양 쪽 리스트의 head를 비교해 더 작은 값을 head로, 나머지 값들로 재귀호출을 한다.

다른 정렬 알고리즘도 대부분 마찬가지지만, mutable 콜렉션으로 구현하는게 훨씬 어려울 것 같다.