[알고리즘 with JS] 합병 정렬 (merge sort)

합병 정렬은 분할 + 정렬 + 병합으로 이루어진 정렬로,
주어진 배열이 단일 요소가 될 때까지 분할한 후 정렬해 가며 합병한다.

 

합병 정렬은 분할, 합병으로 나눌 수 있는데
배열을 합칠 때는 주어진 배열이 정렬되어 있어야 한다.

즉, merge(arr1, arr2)가 있다면 각 arr1, arr2는 정렬되어 있어야 한다.

 

가장 먼저 합친 배열을 담을 빈 배열이 필요하다.

그리고 while문을 돌며 각 배열의 첫 번째 요소끼리 비교를 시작하며

arr1의 첫 번째 요소가 더 작다면 해당 요소를 빈 배열에 넣고

인덱스를 증가시킨다. 

위 과정을 반복하여 배열을 합병시키는 것이다.

function merge(arr1, arr2) {
  let result = [];
  let i=0, j=0;
  while(i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      result.push(arr1[i]);
      i++;
    } else {
      result.push(arr2[j]);
      j++;
    }
  }
  // 두 배열 길이가 달라 하나의 배열만 남았을 경우
  while (i < arr1.length) {
    result.push(arr1[i]);
    i++;
  }
  while (j < arr2.length) {
    result.push(arr2[j]);
    j++;
  }
  return result;
}

그리고 배열을 분할하는 방법은 배열 길이를 사용해
중간 인덱스를 구한 후, slice 메서드를 사용하는 것이다.

분할은 주어진 배열이 단일 요소가 될 때까지 재귀적으로 수행한다.

// 분할 (재귀적으로 수행)
// 중간 인덱스를 구한 후 slice 메서드를 사용해 분할
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));

아래는 병합 정렬의 전체 코드이다.

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

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);
}

mergeSort([10, 24, 76, 73])

-> left: mergeSort([10, 24])

--> left: mergeSort([10]) => [10]

--> right: mergeSort([24]) => [24]

* left, right 값이 나왔으니 merge

=> merge([10], [24]) => [10, 24]

 

-> right: mergeSort([76, 73])

--> left: mergeSort([76]) => [76]

--> right: mergeSort([73]) => [73]

* left, right 값이 나왔으니 merge

=> merge([76, 73]) => [73, 76]

 

* left, right 값이 나왔으니 merge

=> merge([10, 24], [73, 76])

=> [10, 24, 73, 76]

 

따라서 mergeSort([10, 24, 76, 73]) => [10, 24, 73, 76]이 된다.