advancedsorting.md

Advanced sorting instructor notes

• Implement a merge sort algorithm in Javascript
• Implement a quick sort algorithm in Javascript

Implement a merge sort algorithm in Javascript

• Manually work through the merge sort algorithm.
• Implement merge sort.

Implement a quick sort algorithm in Javascript

• Manually work through the quick sort algorithm.
• Implement quick sort.

function partition(arr, left, right) {
  let pivotValue = arr[left];
  let partitionIndex = left;

  for (let i = left + 1; i <= right; i++) {
    if (arr[i] < pivotValue) {
      partitionIndex++;
      swap(arr, i, partitionIndex);
    }
  }

  swap(arr, left, partitionIndex);
  return partitionIndex;
}

function quickSort(arr, left=0, right=arr.length - 1) {

  if (left < right) {
    let partitionIndex = partition(arr, left, right);
    quickSort(arr, left, partitionIndex - 1);
    quickSort(arr, partitionIndex + 1, right);
  }

  return arr;
}