Merge Sort (합병 정렬)

합병 정렬이란

배열의 길이가 0 또는 1이 될때 까지 나누고 (배열의 길이가 0 또는 1이면 이미 정렬된 것으로 봄)

나눠진 배열을 다시 합병하면서 정렬하는 것이다.

 

같은 색깔끼리 같은 하나의 정렬된 배열

 

구현 방법

1. merge 하는 함수 작성

function merge(arr1, arr2) {
  const mergedArr = [];

  let i = 0;
  let j = 0;
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      mergedArr.push(arr1[i]);
      i++;
    } else if (arr1[i] > arr2[j]) {
      mergedArr.push(arr2[j]);
      j++;
    } else {
      mergedArr.push(arr1[i]);
      mergedArr.push(arr2[j]);
      i++;
      j++;
    }
  }
  if (i >= arr1.length && j < arr2.length) return mergedArr.concat(arr2.slice(j));
  else if (j >= arr2.length && i < arr1.length) return mergedArr.concat(arr1.slice(i));

  return mergedArr;
}

function udemyMerge(arr1, arr2) {
  const mergedArr = [];

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

  return mergedArr;
}

2. 재귀함수로 배열을 쪼개고 합치는 함수 구현

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const midIdx = arr.length / 2;
  const leftArr = mergeSort(arr.slice(0, midIdx));
  const rightArr = mergeSort(arr.slice(midIdx));

  const result = merge(leftArr, rightArr);
  return result;
}

console.log(mergeSort([1, 4, 6, 9], [2, 3, 6, 10, 11]));

 

합병정렬에서의 Big O

최적케이스, 평균케이스, 최악케이스 모두 n log n (시간복잡도)

분할할때 O(log n) * 합병할때 O(n) => O(n log n)

공간 복잡도는 O(n) - 버블정렬보다 더 많이 사용한다.