University and coding interviews; the only times you’ll ever need sorting algorithms. Most of the time you’ll only ever need your programming language’s sorting function, .sort() will suffice.

So if you’re a student, or prepping for an interview, or just bored and curious, this blog is for you.

Bogo sort Θ((N+1)!)

Let’s start off with a silly one, bogo sort is simply shuffling the deck and checking to see if it’s ordered. Also know as stupid sort this algorithm has an average time complexity of Average time complexity is O((N-1)* N!).

Bubble sort Θ(n^2)

Bubble sort is probably the simplest of all the algorithms (excluding bogo), all you do is go through your list check the first number against the second number, if the first is bigger than the second switch their positions, and then move onto the next index. You repeat this process until your list is sorted.

Here’s the meat of the code, I’m using p5.js so this is all bunged into the draw() method which gets called 60 times per second.

  if (arr[currentIndex] > arr[currentIndex + 1]) {
    let temp = arr[currentIndex];
    arr[currentIndex] = arr[currentIndex + 1];
    arr[currentIndex + 1] = temp;
  }

  currentIndex++;
  if (currentIndex >= arr.length) currentIndex = 0;

Here’s a link to the code

Selection sort Θ(n^2)

Selection sort simply goes through the list and finds the smallest number and then adds it to the end of a sorted list. In my example I use just one list and track the indexes:

  let minIndex = 0;
  for (let i = currentIndex; i < arr.length; i++) {
    if (arr[i] < min)  {
      minIndex = i;
      min = arr[i];
    }
  }

  let temp = arr[currentIndex];
  arr[currentIndex] = arr[minIndex];
  arr[minIndex] = temp;
  currentIndex++;
  if (currentIndex >= arr.length) currentIndex = 0;

Here’s a link to the code

Insertion sort Θ(n^2)

Quite similar to selection sort Insertion sort has two parts to the array, sorted and unsorted. You iterate through each unsorted element and compare it back through the sorted array until you find its correct position.

  let currentValue = arr[currentIndex];

  let j = currentIndex - 1;
  while (j >= 0 && arr[j] > currentValue) {
    arr[j + 1] = arr[j];
    j = j - 1;
  }
  arr[j + 1] = currentValue;
  currentIndex++;
  
  if (currentIndex >= arr.length) currentIndex = 0;

Here’s a link to the code

Merge sort Θ(n log(n))

Merge sort is a divide and conquer algorithm. It works by dividing up the list into smaller lists until you’re left with just one element in the list, you then continually merge the lists in order until you have a sorted list.

Because this algorithm requires the concatenation of multiple lists, the visual isn’t all that brilliant. I could have jigged it to perform swaps on an individual list to make the gif more compelling but life’s too short.

The meat of the code is within the merge method:

function merge(left, right) {
  let arr = [];
  while (left.length && right.length) {
    if (left[0].num < right[0].num) {
      arr.push(left.shift());
    } else {
      arr.push(right.shift());
    }
  }
  return [...arr, ...left, ...right];
}

Here’s a link to the code

Quick sort Θ(n log(n))

Quick sort is also a divide and conquer algorithm. You choose a pivot, and from that pivot you create two lists, one list containing values greater than the pivot and values greater than the pivot, the process is repeated on the created lists. There are multiple ways to perform the partition step, I’m using the Lomuto partition scheme:

async function quickSort(myArr, start, end) {
  if (start >= end) {
    return;
  }
  const index = await findPartition(myArr, start, end);
  await Promise.all([
    quickSort(myArr, start, index - 1),
    quickSort(myArr, index + 1, end),
  ]);
}

async function findPartition(myArr, start, end) {
  let val = myArr[end];
  let index = start;
  for (let i = start; i < end; i++) {
    if (myArr[i] < val) {
      await swap(myArr, i, index);
      index++;
    }
  }
  await swap(myArr, index, end);
  return index;
}

Here’s a link to the code, for further information I suggest checking out this blog from which I politely borrowed a portion of the code to help display within a recursive context.