Summary of basic sorting algo. implementations

sorting-algos-summary.js

// Basic summary of different common sorting algorithms. 
// This is just for reference; focus in not on micro-optimising the algo, but just generally highlighting the 
// differences between each algorithm. 
//
// Summaries from Brian Holt's CodePen's
//
// ToCs
// 1. Bubble Sort
// 2. Insertion Sort
// 3. Merge Sort (effectively what Array.prototype.sort uses under the hood (95% of the time))
// 4. Quick Sort

// 1. Bubble sort - O(n^2)
const bubbleSort = nums => {  
  do {
    let swapped = false;
    for (var i = 0; i < nums.length; i++) {
      snapshot(nums);
      if (nums[i] > nums[i+1]) {
        const temp = nums[i];
        nums[i] = nums[i+1];
        nums[i+1] = temp;
        swapped = true;
      }
    }
  } while(swapped);
};

// 2. Insertion sort - O(n^2)
const insertionSort = nums => {  
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] < nums[j]) {
        const spliced = nums.splice(i, 1);
        nums.splice(j, 0, spliced[0]);
      }
    }
  }
};

// 3. Merge Sort - O(n log(n))
const mergeSort = nums => {
  if (nums.length < 2) {
    return nums;
  }
  const length = nums.length;
  const middle = Math.floor(length / 2);
  const left = nums.slice(0, middle);
  const right = nums.slice(middle);
  
  return merge(mergeSort(left), mergeSort(right));
};

const merge = (left, right) => {
  const results = [];
  
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      results.push(left.shift());
    }
    else {
      results.push(right.shift());
    }
  }
  
  return results.concat(left, right);
};

// 4. Quick sort - O(n log(n)) (better space complexity than merge sort)
const quickSort = nums => {
  if (nums.length < 2) return nums;
  
  const pivot = nums[nums.length-1];
  const left = [];
  const right = [];
  
  for (let i = 0; i < nums.length-1; i++) {
    if (nums[i] < pivot) {
      left.push(nums[i]);
    }
    else {
      right.push(nums[i]);
    }
  }
  return [
    ...quickSort(left), 
    pivot, 
    ...quickSort(right)
  ];
};