quicksort.js

// https://en.wikipedia.org/wiki/Quicksort
// Divide and Conquer type.
// Worst Case (Rare): O(n**2)
// Typical: O(NlogN)

const swap = (array, x, y) => {
  array[x] = [array[y], array[y] = array[x]][0];
};

const partition = (array, p, r) => {
  const pivot = array[r];
  let i = p - 1;
  for(let j = p; j < r; j++){
    if(array[j] <= pivot){
      i++;
      swap(array, i, j);
    }
  }

  swap(array, ++i, r);
  return i;
};

const quicksort = (array, p, r) => {
  if(p >= r) {
    return;
  }

  const q = partition(array, p, r);
  quicksort(array, p, q - 1);
  quicksort(array, q + 1, r);
};

// Tail recursion
const tailquicksort = (array, p, r) => {
  while(p < r){
    const q = partition(array, p, r);
    tailquicksort(array, p, q - 1);
    p = q + 1;
  }
};