병합 정렬 알고리즘

병합 정렬이란 ?

병합 정렬이란 각 요소들을 반으로 최대로 나눈후, 그것을 다시 오름차순으로 정렬하면서 합쳐주는 방식을 의미한다.

시간 복잡도는 O(nlogn) 이고, 배열의 내장 sort 메서드가 이 알고리즘을 사용한다.

병합 정렬은 배열을 반으로 나눠주는 mergeSort 함수와 그 분류된 배열을 정렬해서 합쳐주는 merge 함수 2개로 구성되어 있고, mergeSort 함수 내에서 mergeSort 함수를 재귀적으로 호출한다.

- 코드

const arr = [5, 3, 4, 7, 1];

function mergeSort(arr) {
  // 배열 자체의 길이가 2보다 작다면 그냥 그 배열 자체를 반환
  if (arr.length < 2) {
    return arr;
  }

  // 배열의 중앙 인덱스 값 올림해서 구해주기

  const mid = Math.ceil(arr.length / 2);

  // 왼쪽 값
  const left = mergeSort(arr.slice(0, mid));

  // 오른쪽 값
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  let result = [];

  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }

  while (left.length) {
    result.push(left.shift());
  }

  while (right.length) {
    result.push(right.shift());
  }

  return result;
}

console.log(mergeSort(arr));

- mergeSort 함수부분

const arr = [5, 3, 4, 7, 1];

function mergeSort(arr) {
  // 배열 자체의 길이가 2보다 작다면 그냥 그 배열 자체를 반환
  if (arr.length < 2) {
    return arr;
  }

  // 배열의 중앙 인덱스 값 올림해서 구해주기

  const mid = Math.ceil(arr.length / 2);

  // 왼쪽 값
  const left = mergeSort(arr.slice(0, mid));

  // 오른쪽 값
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

처음에 Math.ceil 메서드를 통해 배열이 분할이 되어서 [5, 3, 4]와 [7, 1] 부분으로 나뉘어진다.

그 후에 [5,3,4]로 mergeSort함수가 다시 실행되면서 [5,3]으로 나뉘게 되고 [5]와 [3]으로 분할이 되어서

leftArr에는 [5]가 rightArr에는 [3]이 할당 된다. 그 후에 merge 함수가 실행이 되고

왼쪽 요소가 오른쪽 요소보다 크다면 result에 leftArr[0]값이 할당되고 그게 아니라면 rightArr[0]값이 할당되어서 더 작은 값부터 leftArr에 push 된다 .

이렇게 되면 leftArr이 [3,5]가 되고 그 후에 [4]를 병합하며 다시 정렬한다.