[Algorithm log] MergeSort

mergeSort(병합 정렬)는 배열을 나누어가면서 그룹별로 정렬한 후 다시 합치는 방식으로 정렬한다.

divide and conquer라는 전략을 사용하는 대표적인 정렬이다.

▼

 

분할한 후 

---

비교하면서 정렬시킨다.

이 부분이 중요한 부분인데, L과 R로 나누어 비교하면서 가장 밑에서 모두 합친다. 마치 토너먼트를 하는것 처럼 말이다. 

▼

code

개인적으로 병합정렬의 코드를 이해하는데 참 오래 걸렸다. 한, 1년 정도 걸린 것 같다. 아니, 병합 정렬을 이해하는 것이 오래 걸린 것이 아니라 재귀 함수를 이해하는데 걸린 시간이라고 봐도 될 것 같다. 

function mergeSort(array){
  if(array.length <= 1) {
    return array;
  }else{
    const middleIndex = Math.floor(array.lenght/2);
    // divide
    const leftArray = mergeSort(array.slice(0,middleIndex));
    const rightArray = mergeSort(array.slice(middleIndex));
    
    // conquer
    const result = [];
    while(leftArray.length && rightArray.length){
      if(leftArray[0] < rightArray[0]){
        result.push(leftArray.shift());
      }else{
        result.push(rightArray.shift());
      }
    }
    while(leftArray.length){
      result.push(leftArray.shifht());
    }
    while(rightArray.length){
      result.push(rightArray.shift());
    }
    return result;
  }
}

mergesort는 재귀 함수다. 재귀 함수는 탈출 조건을 명시하지 않으면 callstack이 넘쳐 오류가 난다. 병합 정렬에서의 재귀 탈출 조건은 배열의 길이가 1 이하가 되면 리턴한다. 이것이 시작점이기 때문이기도 하다.

middleIndex를 기준으로, 왼쪽과 오른쪽으로 mergeSort를 실행한다. 실행결과는 배열이 나올 테니 나온 배열로 합쳐주는 작업을 하는 것이다.

while 부분은 합쳐진 배열들을 가지고 정렬 작업을 해주는 곳이다. 이 부분에서 push, shift의 메서드를 사용해서 배열을 직접 고쳐준다.

마지막에 return 된 result는 아래 스택에 쌓인 mergerSort에 leftArray 혹은 rightArray가 되고 (여기에서 토너먼트가 되는 것이다.)

가장 아래 스택에 쌓인 mergeSort에 최종 값이 들어간다.

---

콜 스택에 쌓인 그림을 보면 조금 더 명확하게 이해할 수 있을 것이다.

왼쪽 부분만 그려봤다. 오른쪽도 마찬가지로 이렇게 되기 때문이다.

재귀 함수의 전체 그림이 그려지지 않는다면 아마 병합 정렬을 코드로 표현하기 힘들것이다.

병합 정렬의 시간 복잡도는 O(nlogn)으로 성능이 꽤 좋다. 하지만 정렬된 배열을 가지고 있어야 해서 메모리를 추가적으로 가져간다.

처음 재귀 함수를 배웠을 때 재귀 함수는 굉장히 쉬운 줄 알았다. factorial을 재귀로 이렇게 구하면 되는구나~ 하고 말이다.

근데 다른 곳에 응용을 하려고 하니깐 전혀 되지 않는 것이다. 지금도 헷갈릴 때가 있지만 전보다는 조금 더 이해가 되었다.

병합 정렬의 핵심은 재귀 함수를 "잘" 쓰자 인 것 같다.