Sorting algorithms

quick-sort.js

{
// Reference: https://bit.ly/2yjWDeY
// Time complexity: O(n log n) on average or O(n^2) for worst-case
// Space complexity: O(n)

function quickSort(list) {
  if (list.length < 2) return list;

  const left = [];
  const right = [];
  const pivot = list.shift();
  const len = list.length;
  let i = 0;

  while (i < len) {
    const val = list[i];

    if (val <= pivot) left.push(val);
    else right.push(val);

    i += 1;
  }

  return quickSort(left).concat(pivot, quickSort(right));
}

a = [1, 4, 6, 8, 2, 3, 7, -1, 0];

b = [...a];
console.time('quickSort');
quickSort(b);
console.timeEnd('quickSort');

c = [...a];
console.time('sort');
c.sort();
console.timeEnd('sort');

quickSort([...a]);
}