Merge sort

Sorting은 일반적으로 검색과 함께 사용된다.

Sorting 된 리스트는 그렇지 않은 리스트보다 검색하기가 더 쉽다.

 

주어진 리스트의 요소들을 정렬하는 방법은 많다.

이번 글에서는 Merge sort에 대해 알아본 내용을 정리해보려고 한다.

Merge sort

Merge sort는 인기 있는 방법 중 하나이며, 효율적인 방법이다.

 

Logic

Merge sort는 문제를 직접적으로 풀기 충분할 때까지 반복하여 주어진 배열을 쪼갠다.

 

다음 4가지 단계를 통해 그 과정을 확인해보자.

1. 배열을 절반씩 두 개로 쪼갠다(홀수일경우 최대한 절반씩).
2. 하나의 요소만을 가진 배열이 될 때까지  1번의 방식을 반복한다.
3. 단일 요소 배열에서부터 시작하여, 배열을 합쳐서 sort 한다.
4. 하나의 정렬된 배열이 될 때까지 3번을 반복한다.

Merge sort 구현하기

로직을 기반으로 [4, 8, 7, 2, 11, 1, 3]을 정렬해보자.

 

function merge(left, right) {
    let arr = []
    // Break out of loop if any one of the array gets empty
    while (left.length && right.length) {
        // Pick the smaller among the smallest element of left and right sub arrays 
        if (left[0] < right[0]) {
            arr.push(left.shift())  
        } else {
            arr.push(right.shift()) 
        }
    }
    
    // Concatenating the leftover elements
    // (in case we didn't go through the entire left or right array)
    return [ ...arr, ...left, ...right ]
}

merge 코드의 원리는 이렇다.

 

분리된 두 배열의 첫 번째 값을 비교하여 작은 값을 arr에 push 하며 한쪽이 빈 배열이 될 때까지 반복한다.

한 쪽이 빈 배열이 되면 arr과 두 배열을 붙여 반환한다.

 

작은 값부터 정렬되어있는 arr의 뒤에 두 배열을 붙여줌으로써 정렬된 하나의 배열을 반환한다.

 

function mergeSort(array) {
  const half = array.length / 2
  
  // Base case or terminating case
  if(array.length < 2){
    return array 
  }
  
  const left = array.splice(0, half)
  return merge(mergeSort(left),mergeSort(array))
}

 

mergeSort 함수는 초기에 주어진 배열을 반으로 나누는 함수이다.

 

base case로 주어진 배열의 길이가 하나일 때 배열을 그대로 반환한다.

 

그게 아니라면 아래의 재귀 함수 형식이 되어 하나가 남을 때까지 반복하여 배열을 나눈다.

 

이 과정을 이해하기 위해 직접 노트에 그려보았다.

한 장에 담아 내고자 고집부렸더니 보기 힘든 풀이가 되었다..

 

아무튼 핵심은 단일 배열이 될 때까지 나눈다는 것!

 

Merge sort

merge sort의 시간 복잡도는 빅오 기준으로 O(n log n)이다.

이는 Quick sort와 같으며 가장 빠른 정렬 알고리즘 중에 하나라는 것을 알 수 있다.

 

하지만 Quick sort처럼 내부 정렬을 하는 것이 아니기 때문에(merge sort는 변수 arr 사용),

추가적인 입력 공간이 필요하다.

따라서 공간 복잡도는 O(n)이다.

 

또한 전체 배열 각각 절반의 배열들은 자체적으로 정렬되어있기 때문에 다중 스레드에 매우 적합하다.