Merge Sort(합병 정렬) 알고리즘

Merge Sort

분할, 정렬, 합병 3가지의 단계로 이루어진 알고리즘으로 배열의 아이템이 0개 혹은 1개일경우 어떠한 값이 오든 배열은 정렬된 상태인것을 이용하는 방식이다.

전체 배열을 0 혹은 1개의 아이템이 남을때까지 계속해서 2분할 한후 1개의 아이템을 가진 배열 2쌍씩 비교하여 정렬후 합병하며 전체 배열이 정렬될때까지 계속해서 비교후 정렬, 합병을 반복한다.

 

병합 함수

Merge Sort의 마지막단계인 정렬과 합병을 수행할 함수를 먼저 만들어 준다.

function merge(arr1, arr2) {
  let result = [];
  let i = 0;
  let j = 0;

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

1. 마지막에 정렬된 배열을 반환할 빈배열 "result"와 첫번째 배열의 카운터 "i" 두번째 배열의 카운터 "j"를 변수로 생성해준다.
2. while문을 이용하여 각각의 카운터 i혹은 j가 각 배열의 마지막에 도달하지 않았다면 계속해서 반복문을 수행하도록 해준다.
3. 첫번째 배열과 두번째 배열의 첫번째 아이템을 비교, 이후 더 작은값을 빈배열 result에 추가 해준뒤 다음 비교를위해 i 혹은 j 값을 +1해준다.
4. 만약 비교된 두값이 같다면 두값 모두 result에 추가, 이후 i와 j 모두 +1해주어 다음 값들을 비교한다.
5. 첫번째 while문을 통해 두 배열간의 비교가 끝나더라도 비교되지 않은 값이 남아있다면 남은 값들은 다른 배열의 제일 큰 값보다 크다는 것을 의미하므로 두번째와 세번째 while문을 통해 남은 값들을 순차적으로 result에 추가해준다.

 

분할 함수

Merge Sort의 첫번째 단계인 분할을 수행하며 재귀함수를 사용하고 분할을 수행하면서 병합함수를 호출한다.

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

 

 

위에 설명했다시피 배열을 0개 혹은 1개의 아이템이 남을때까지 분할 시켜야 되므로 base case로는 배열이 1개 이하의 아이템을 가지고있을때 그 배열을 리턴해준다.

recursive case로는 배열을 계속해서 2분할 해주므로 slice함수를 이용하여 첫번째 배열은 첫아이템부터 중앙의 아이템까지 재귀함수를 실행, 두번째 배열은 중앙 아이템부터 마지막아이템까지를 재귀함수로 실행후 반환되는 리턴값을 병합함수로 정렬, 병합 단계를 수행해주면된다.

 

 

Merge Sort가 실행되는 과정

위와 같이 함수를 실행하면 처음 mergeSort 함수를 통해 반으로 분할 이후 계속해서 재귀함수로 배열의 아이템이 1개가 남을때까지 분할이 되며 이후 리턴값을 이용해 merge 함수가 실행되어 정렬후 병합이 이뤄진다.

 

 

Merge Sort의 Big O notation

총 8개의 아이템이 있는 배열이 분할할때 3번의 분할만으로 모든 아이템이 분할되므로 분할의 과정에서의 시간복잡도는 O(log n)이 된다. 이후 정렬단계에서 배열의 모든값들이 비교후 정렬되므로 O(n)이 되며 최종 시간복잡도는 O(n log n)이 된다. 배열의 순서에 상관없이 모든과정이 똑같이 이뤄지므로 best, average, worst 모두 O(n log n)이 된다.