병합 정렬

function merge(arr, left, mid, right) {
  const leftArrLength = mid - left + 1; // 완쪽 배열의 길이
  const rightArrLength = right - mid; // 오른쪽 배열의 길이
  
  // 왼쪽 배열의 길이 만큼 임시 배열 생성
  const leftArr = new Array(leftArrLength); 
  
  // 오른쪽 배열의 길이 만큼 임시 배열 생성
  const rightArr = new Array(rightArrLength);
 
  // 왼쪽 배열에 알맞은 요소를 추가
  for (let i = 0; i < leftArrLength; i++) {
    // left + i : 기준을 left 값(왼쪽 배열의 첫번째 index)을 가지고 알맞은 요소를 하나씩 추가한다.
    leftArr[i] = arr[left + i];
  }
  
  // 오른쪽 배열에 알맞은 요소를 추가
  for (let i = 0; i < rightArrLength; i++) {
    // mid + 1 + i : 기준을 mid + 1 값(오른쪽 배열의 첫번째 index)을 가지고 알맞은 요소를 하나씩 추가한다.
    rightArr[i] = arr[mid + 1 + i];
  }
  
  let i = 0;
  let j = 0;
  let k = left;
  
  // 왼쪽 배열과 오른쪽 배열의 각 첫번쨰 요소 부터 비교하여 정렬 후에 배열 arr에 추가한다. (결합)
  while (i < leftArr.length && j < rightArr.length) {
    if (leftArr[i] <= rightArr[j]) {
      arr[k] = leftArr[i];
      i++;
    } else {
      arr[k] = rightArr[j];
      j++;
    }
    
    k++;
  }
  
  // 왼쪽 배열의 남은 요소들을 배열 arr에 추가한다.
  while (i < leftArrLength) {
    arr[k] = leftArr[i];
    i++;
    k++;
  }
  
  // 오른쪽 배열의 남은 요소들을 배열 arr에 추가한다.
  while (j < rightArrLength) {
    arr[k] = rightArr[j];
    j++;
    k++;
  } 
}

// left은 하위 배열의 왼쪽 인덱스이고 right은 하위 배열의 오른쪽 인덱스입니다.
function mergeSort(arr, left, right) {
  if (left >= right) {
    return;
  }
  
  const mid = parseInt((left + right) / 2); // 중간 위치
  
  mergeSort(arr, left, mid); // 0 ~ 중간 위치까지 배열
  mergeSort(arr, mid + 1, right); // 중강 위치 + 1 ~ 마지막 요소까지 배열
  merge(arr, left, mid, right); // 분할한 배열을 정렬하여 결합하는 과정
}

const tempArr = [ 12, 11, 13, 5, 6, 7 ];

mergeSort(tempArr, 0, tempArr.length - 1);

console.log(tempArr); // [5, 6, 7, 11, 12, 13]