[Algorithm]Sort-Merge sort

병합 정렬(Merge Sort)은 배열을 더 작은 하위 배열로 분할하여 정렬한 다음 올바른 순서로 원래 배열로 다시 병합하여 정렬하는 분할 정복 알고리즘이다. 이 알고리듬은 최상의 시나리오와 최악의 시나리오 모두에서 안정성과 일관된 성능으로 알려져 있다.

병합 정렬의 기본 아이디어는 이미 정렬된 단일 요소에 도달할 때까지 배열을 계속 절반으로 분할하는 것입니다. 그런 다음 정렬된 하위 배열을 병합하여 더 큰 정렬된 새 배열을 만듭니다.

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  
  // Divide the array in half
  const middleIndex = Math.floor(arr.length / 2);
  const left = arr.slice(0, middleIndex);
  const right = arr.slice(middleIndex);
  
  // Recursively sort the sub-arrays
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);
  
  // Merge the sorted sub-arrays
  return merge(sortedLeft, sortedRight);
}

function merge(left, right) {
  let i = 0;
  let j = 0;
  const mergedArray = [];
  
  // Merge the sub-arrays by comparing their elements
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      mergedArray.push(left[i]);
      i++;
    } else {
      mergedArray.push(right[j]);
      j++;
    }
  }
  
  // Add any remaining elements to the merged array
  while (i < left.length) {
    mergedArray.push(left[i]);
    i++;
  }
  
  while (j < right.length) {
    mergedArray.push(right[j]);
    j++;
  }
  
  return mergedArray;
}

이 구현에서는 먼저 배열에 요소가 하나만 있는지 또는 비어 있는지 확인하고, 있으면 배열을 그대로 반환합니다. 그런 다음 슬라이스()를 사용하여 배열을 반으로 나누어 왼쪽 및 오른쪽 하위 배열을 만듭니다.

다음으로 왼쪽 및 오른쪽 배열에서 mergeSort를 호출하여 하위 배열을 재귀적으로 정렬합니다.

마지막으로 병합 함수를 사용하여 정렬된 하위 배열을 다시 병합합니다. 병합 기능은 왼쪽 및 오른쪽 배열의 요소를 반복하여 비교함으로써 작동합니다. 병합된 새로운 어레이에 작은 요소를 추가한 다음 작은 요소를 가진 하위 어레이의 인덱스를 증가시킵니다. 두 하위 어레이의 모든 요소를 비교하고 병합된 어레이에 추가할 때까지 이 프로세스를 계속합니다.

결론적으로, 병합 정렬은 분할 정복 접근법을 사용하여 배열을 더 작은 하위 배열로 분할한 다음 다시 올바른 순서로 병합하여 정렬하는 널리 사용되는 정렬 알고리즘이다. 최상의 시나리오와 최악의 시나리오 모두에서 일관된 성능을 갖는 안정적이고 효율적인 알고리즘이다. 이 알고리즘은 자바스크립트에서 구현하기 쉽고 대규모 데이터 세트를 정렬하는 데 사용할 수 있다.