[정렬 알고리즘] #5. 합병 정렬 (Merge Sort)

합병 정렬

분할 정복 알고리즘 중 하나이고 안정 정렬에 속하는 정렬 알고리즘이다.

알고리즘

합병 정렬은 다음과 같이 진행된다.

 

• Divide: 입력으로 받은 배열을 같은 크기의 2개의 배열로 길이가 1이 될 때까지 나눈다. (배열의 길이가 1일 때 배열이 정렬이 된 상태라고 본다.)
• Conquer: 2개의 정렬된 배열을 하나의 배열로 정렬을 하면서 합친다.

1. 입력으로 받은 배열을 배열의 길이가 1개가 될 때까지 절반으로 나눠준다.
2. 2개의 정렬된 배열을 서로 인덱스 0부터 비교하면서 더 작은 값을 또 다른 배열에 넣어준다.
3. 2개의 배열 중 하나의 배열에서 모든 값을 새로운 배열에 넣을 때까지 반복한다.
4. 만약 하나의 배열의 값들을 모두 넣어주면 남은 배열의 값들은 새로운 배열에 push 한다.
5. 나눠진 모든 배열들이 합쳐질 때까지 반복한다.

// 자바스크립트 코드
const merge = (leftArr, rightArr) => {
  const sortedArr = [];
  let leftIndex = 0;
  let rightIndex = 0;
  while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
    if (leftArr[leftIndex] <= rightArr[rightIndex]) {
      sortedArr.push(leftArr[leftIndex++]);
    } else {
      sortedArr.push(rightArr[rightIndex++]);
    }
  }

  return [
    ...sortedArr,
    ...leftArr.slice(leftIndex),
    ...rightArr.slice(rightIndex),
  ];
};

const mergeSort = (arr) => {
  if (arr.length === 1) return arr;

  const mid = Math.ceil(arr.length / 2);
  const leftArr = arr.slice(0, mid);
  const rightArr = arr.slice(mid);

  return merge(mergeSort(leftArr), mergeSort(rightArr));
};

특징

• 입력 데이터가 무엇이든 정렬되는 속도는 동일하다. 
• 합병을 할 때는 O(log n)의 시간복잡도를 가지고 각 합병 단계에서 2개의 배열을 비교할 때는 O(n)의 시간복잡도를 가진다.
• 따라서, O(n log n) 의 시간 복잡도를 가진다.