Algorithm - Merge Sort

Bubble, Selection, Insertion Sort 단점

• 배열의 길이가 엄청 커지면 정렬 시간이 오래 걸림 (시간복잡도가 O(N^2)이므로)

Merge Sort

• merging과 sorting의 조합임
• 배열의 요소가 0개 또는 1개인 배열은 항상 정렬되어 있다는 사실을 이용함
• 배열을 0 ~ 1개 요소를 가진 배열로 분해하고, 새로 정렬된 배열을 만듬

Merging Arrays

• merge sort를 실행하기 위해서, 첫 번째로 두 정렬된 배열을 병합하는 함수를 실행해야 함

  • 이 함수는 두 정렬된 배열이 주어졌을 때 두 배열의 모든 요소로 구성되어 있고 정렬된 새로운 배열을 반환함
  • 이 함수의 시간 복잡도, 공간 복잡도는 모두 O(n+m)임
  • 전달되는 매개변수들을 변경하면 안 됨

• 두 정렬된 배열을 병합하는 함수 시나리오

  • 빈 배열을 생성하고, 각 배열의 가장 작은 값을 선택하기

  • 배열을 모두 순회할 때까지 while 문을 실행함

    • 첫 번째 배열의 값이 두 번째 배열의 값보다 작으면, 첫 번째 배열의 값을 결과 배열에 삽입하고 첫 번째 배열의 다음 값으로 이동함
    • 첫 번째 배열의 값이 두 번째 배열의 값보다 크면, 두 번째 배열의 값을 결과 배열에 삽입하고 두 번째 배열의 다음 값으로 이동함
    • 한 배열이 먼저 순회될 경우, 다른 배열의 나머지 값들을 결과 배열에 모두 삽입함

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

Merge Sort function

• 배열이 비거나 하나의 요소만 가질 때까지 배열을 반으로 나눔
• 가장 작은 배열들을 가지면, 그 배열들을 다른 정렬된 배열들과 병합해서 하나의 큰 배열로 만듬
• 병합된 배열을 반환함

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

console.log(mergeSort([10, 24, 76, 73, 4, 1]));

Big O of mergeSort

• Time Complexity : O(NlogN) (Best ~ Average ~ Worst)
  • O(logN) 배열 분해 + O(N) 배열의 요소만큼 비교해서 병합
• Space Complexity : O(N)