Algorithm / 정렬 / Merge Sort (합병 정렬)

합병 정렬

function merge(left_arr, right_arr) {
  let result = [];
  let [i, j] = [0, 0];

  while (i < left_arr.length && j < right_arr.length) {
    if (left_arr[i] < right_arr[j]) {
      result.push(left_arr[i]);
      i++;
    } else {
      result.push(right_arr[j]);
      j++;
    }
  }

  while (i < left_arr.length) {
    result.push(left_arr[i]);
    i++;
  }
  while (j < right_arr.length) {
    result.push(right_arr[j]);
    j++;
  }

  return result;
}

function merge_sort(arr) {
  if (arr.length <= 1) return arr;

  let mid_idx = Math.floor(arr.length / 2);
  let left_arr = merge_sort(arr.slice(0, mid_idx));
  let right_arr = merge_sort(arr.slice(mid_idx));

  return merge(left_arr, right_arr);
}

let arr = [3, 6, 13, 4, 33, 12, 35, 87, 6, 64];
const result = merge_sort(arr);
console.log(result);

---

1. 입력(배열) 두개를 받을 함수를 선언하며, 마지막에 결과값을 넣어서 반환할 빈 배열을 하나 만든다.
   1. 각 입력의 가장 작은 값부터 시작한다.
2. 아직 살펴보지 않은 값이 있다면,
   1. 첫번째 배열에 있는 값이 두번째 배열에 있는 값보다 작다면, 결과값에 push 하고 다음순서를 밟는다.
   2. 만약 두번째 배열에 있는 값이 더 크다면, 두번째 배열을 결과값에 push 하고 두번째 배열의 다음 값을 살펴본다.
   3. 배열 하나를 완료하면 다른 배열은 그대로 넣어준다. (전 단계에서 이미 정렬되어 있을 것이다.)

 

시간 복잡도: O(n log n)

• 최악, 평균, 최선 모두 같은 시간 복잡도를 가진다.
• 입력값이 무엇이든 똑같이 최소의 엘리먼트를 가지는 배열로 나눈뒤 합하면서 정렬을 수행하기 때문이다.
  
  
• 시간 복잡도에 log n이 들어가는 이유는,
  • 아래와 같이 밑이 2고 지수가 요소의 개수를 가지는 log의 값만큼 분할이 일어나기 때문이다.
    
    

• 시간 복잡도에 n이 들어가는 이유는,
  • 합병할때 n번의 합병을 거치기 때문이다.
  • [1,3] 과 [2,4]의 두 배열을 합병한다고 해보자.
    1. 1과 2를 비교하여 result에 1을 push 하므로 result = [1]
    2. 3과 2를 비교하여 result에 2를 push 하므로 result = [1,2]
    3. 3과 4를 비교하여 result에 3을 push 하므로 result = [1,2,3]
    4. 마지막으로 4를 push하여 result = [1,2,3,4] 가 된다.
  • 위 그림으로 살펴보자면 3의 단계에서 아래에서 위로 합병하는 경우를 생각하면 된다.

 

 

공간 복잡도: O(n)

• 배열이 길어질수록 분할하면서 생기는 sub배열들을 저장할 공간이 더 필요하므로 공간 복잡도는 크다.