[알고리즘] 합병정렬

1. 합병정렬

기존 버블, 선택, 삽입정렬은 O(N^2)의 시간복잡도를 가진다.

합병정렬을 통해 o(NlogN)으로 향상시킬 수 있다.

합병 정렬은 분해와 합병 2가지 순서로 나눌수 있다.

 

예시 )

[8,3,5,4,7,6,1,2]
반으로 분할하여 시작
[8,3,5,4]  [7,6,1,2]
다시 나눔
[8,3] [5,4] [7,6] [1,2]
다시 나눔
[8] [3] [5] [4] [7] [6] [1] [2] 
정렬하면서 합친다.
[3,8] [4,5] [6,7] [1,2]
[3,4,5,8] [1,2,6,7]
[1,2,3,4,5,6,7,8]

2. 합병정렬 순서

(1) 빈배열 만들기, 입력 두개를 취하는 함수를 정의하여 마지막에 반환할 빈 뱅열 만들기

(2) i와 j가 각각 배열끝에 도달하지 않았다면 첫번째 배열의 값으로 첫번째 항목을 취한 다음 두번째 배열의 첫번째 항목값과 비교한다.

(3) 첫번째 항목이 더 작다면 결과배열에 집어넣은 다음 첫번째 배열의 다음 항목으로 넘어간다.

     반대의 경우에는 두번째 배열의 값을 취한 다음 두번째 배열의 다음값으로 넘어간다.

(4) 배열 하나를 완료한 다음에는 다른 배열의 남은 값을 모두 넣는다.

 

예시)

 [1,10,50] [2,14,99,100]
 1,2 비교후 1을 배열에 집어넣는다.
 [1]  
 다음 10 과 2를 비교후 작은값을 넣는다.
 [1,2]
 다음 10,14비교
 [1,2,10]
 반복
 [1,2,10,14,50]
 첫번째 배열이 끝났을때는 나머지 배열을 전부 넣어준다.
 [1,2,10,14,50,99,100]

3. 합병 구현

정렬하며 합치는 함수부터 구현한다.

function merge(arr1, arr2) {
  let i = 0;
  let j = 0;
  let temp = [];
  while (i < arr1.length || j < arr2.length) {
    if (i == arr1.length) {
      temp.push(arr2[j]);
      j++;
    } else if (j == arr2.length) {
      temp.push(arr2[i]);
      i++;
    } else {
      if (arr1[i] < arr2[j]) {
        temp.push(arr1[i]);
        i++;
      } else {
        temp.push(arr2[j]);
        j++;
      }
    }
  }
  return temp;
}

4. 합병 정렬 구현

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

5. 합병정렬 빅O

시간복잡도(최고)	시간복잡도(평균)	시간복잡도(최악)	공간복잡도
O(nlogn)	O(nlogn)	O(nlogn)	O(n)