[JS] 정렬

1. 병합 정렬

function merge(left, right) {
  const res = Array(left.length + right.length);

  let resIndex = 0;
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      res[resIndex] = left[leftIndex];
      leftIndex += 1;
    } else {
      res[resIndex] = right[rightIndex];
      rightIndex += 1;
    }

    resIndex += 1;
  }

  while (leftIndex < left.length) {
    res[resIndex] = left[leftIndex];
    leftIndex += 1;
    resIndex += 1;
  }

  while (rightIndex < right.length) {
    res[resIndex] = right[rightIndex];
    rightIndex += 1;
    resIndex += 1;
  }

  return res;
}

function mergeSort(arr) {
  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);
}

2. 빠른 정렬

function swap(arr, index1, index2) {
  const temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
}

function partition(arr, left, right) {
  const mid = Math.floor((left + right) / 2);
  const pivot = arr[mid];

  while (left <= right) {
    while (pivot > arr[left]) left += 1;
    while (pivot < arr[right]) right -= 1;

    if (left <= right) swap(arr, left++, right--);
  }

  return left;
}

function quickSort(arr, left, right) {
  const index = partition(arr, left, right);
  if (left < index - 1) quickSort(arr, left, index - 1);
  if (index < right) quickSort(arr, index, right);

  return arr;
}