Sorting Algorithms in JavaScript

Ever since I first heard about Sorting Algorithms they’ve always been synonym great fun!

Organising elements from a list is something that is very often required in our daily life, most usually the order is very straight forward like numerical or respecting some priority flag. Nevertheless, developers nowadays are very abstracted from their implementations.

Although the problem is quite simple, the solutions are not very straight forward, speaking by myself, I often see myself revisiting the most common algorithms. A few months ago I decided to implement, in JS, 4 of the most sorting algorithms:

• Insertion Sort;
• Bubble Sort;
• Merge Sort;
• Quick Sort.

Hope this article can help you clarify their concept and provide you with a simple implementation.

Insertion Sort

function insertionSort(arrayToSort) { 
  for (let i = 1; i < arrayToSort.length; i++) {  
    let j = i;  
    while (j > 0 && arrayToSort[j-1] > arrayToSort[j]) {   
      swap(arrayToSort, j-1, j);
      j--;   
    } 
  } 
  return arrayToSort;
}

Insertion Sort works by taking elements from the list one by one and then comparing the values with the values already visited inside the current list. By the end of n iterations we guarantee that the n elements are sorted.

* Worst-case O(n^{2}) comparisons
* Best-case O(n) comparisons

Bubble Sort

function bubbleSort(arrayToSort) {
  for (let i = 0; i < arrayToSort.length; i++) {
    for (let j = 0; j < (arrayToSort.length - i - 1); j++) {
      if (arrayToSort[j] > arrayToSort[j+1]) {
        swap(arrayToSort, j, j+1);
      }
    }   
  }
  return arrayToSort;
}

Bubble Sort is both quite simple and inefficient. Efficiency will depend on the list given as input, but most times is only efficient when used in an almost-sorted/sorted list.

* Worst-case O(n^{2}) comparisons
* Best-case O(n^{2}) comparisons — could be O(n) if added an extra check to verify if array is already sorted

Merge Sort

function mergeSort(arrayToSort) {
  if (arrayToSort.length === 1) {
    return arrayToSort;
  }
  const middle = Math.floor(arrayToSort.length / 2);
  const left = arrayToSort.slice(0, middle); 
  const right = arrayToSort.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
  let result = [];
  while (left.length && right.length) {
    if (left[0] > right[0]) {
      result.push(right.shift());
    } else {
      result.push(left.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length){
    result.push(right.shift());
  }
  return result;
}

Merge Sort takes advantages on merging already sorted lists. Implementation starts by breaking input list into two separates lists and recursively breaks into smaller pieces focusing on keeping the separated lists organised and maintaining the left side “smaller” than the right side.

* Worst-case O(n log n) comparisons
* Best-case O(n log n) comparisons

Quick Sort

function quickSort(arrayToSort) {
  if (arrayToSort.length <= 1) {
    return arrayToSort;
  }
  let left = [];
  let right = [];
  let result = [];
  let pivot = arrayToSort.shift();
  
  for (let i=0; i < arrayToSort.length; i++) {
    if (arrayToSort[i] > pivot) {
      right.push(arrayToSort[i]);
    } else {
      left.push(arrayToSort[i]);
    }
  }
  return result.concat(quickSort(left), pivot, quickSort(right));
}

Quick Sort is great of big lists. Uses the divide and conquer approach. Algorithm selects a pivot and from that pivot break the list into smaller pieces lists. Keep in mind that selecting a good pivot (pivot should be closer to median as possible, in current implementation I’m picking up the first element) can dramatically increase efficiency. This algorithm execution can be easily distributed using multithreading approach.

* Worst-case O(n log n) comparisons
* Best-case O(n log n) comparisons

I used a swap function in some algorithms. This function should be something like this:

function swap(arrayToSwap, firstIndex, secondIndex) {
  const temp = arrayToSwap[firstIndex];
  arrayToSwap[firstIndex] = arrayToSwap[secondIndex];
  arrayToSwap[secondIndex] = temp;
}

There’s plenty of more information regarding Sorting Algorithms available, feel free to explore. I also created a public GitHub repo with this code:
https://github.com/JMGomes/SortingAlgorithms/

On that repo, you will find that I replaced the normal compare statement (value1 > value2) with an abstract function called customCompare(). This allows users to use a more complex compare statement, e.g. reading object property.

Using that repo, you can also pass your custom input arrays and compare yourself by executing time for each algorithm. Is the most fun part, imo.

Thanks