Merge Sort (with JavaScript)

# Merge Sort

시간 복잡도가 O(nlogn)인 매우 효율적인 정렬 알고리즘 중 하나로 다음과 같은 특징을 가진다.

• comparison sort: 비교 연산자를 통한 sorting이다.
• divide-conquer algorithm: Input을 여러 partition으로 나누어 정렬하는 작업을 재귀적으로 진행한다.
• stable sort: 같은 값을 가지는 index에 대하여 index 순서가 유지되며 정렬된다.
• Linked list를 사용할 경우 in-place로 구현 가능하다. (array의 경우 불가)

기본적인 특징들은 quick sort와 매우 유사하나 일반적으로 quick sort보다 약간 느리다고 한다.

하지만 quick sort는 최악의 경우 O(n²)의 시간 복잡도를 가지는데 반해 merge sort는 최악의 경우에도 O(nlogn)를 보장한다.

 

# Process

Merge sort는 크게 두 단계의 동작에 의해 수행된다.

1. Unsorted list를 절반씩 반복하여 나눈다. 크기가 1이 될 때까지 나눈다.
2. 나누어진 sublist를 하나씩 병합시킨다. 이 때 각 sublist의 element의 크기를 비교하며 병합한다.

# JavaScript로 구현

In-place로 구현하기 위해선 linked list를 사용해야 하지만, JavaScript에서는 기본적으로 지원하는 linked list가 없으므로 간편하게 array로 구현하였다.

// merge sort
function mergeSort(array) {
  if (array.length === 1) return array; // 종료 조건

  // divide
  const middleIndex = Math.floor(array.length/2);
  const left = mergeSort(array.slice(0, middleIndex));
  const right = mergeSort(array.slice(middleIndex, array.length));
  
  // merge
  const result = [];
  while (left.length !== 0 && right.length !== 0) {
    if (left[0] <= right[0]) result.push(left.shift());
    else result.push(right.shift());
  }
  return [...result, ...left, ...right];
}