Today's recommendation from ChatGPT was "Algorithms"–yup, just that, in one day, master all algorithms 🤣. But as reality set in, I wanted to narrow down to some algorithms I'm familiar with and try to see if I can dig into them past the high level understanding. I chose sorting algorithms specifically because it gives me a constraint. Searching algorithms could be a whole college course of their own so I'm not gonna get into those today.

Common sorting algorithms

At this point, I'm writing from the top of my head, all things I'm familiar with and then I'll go deeper into what things I don't understand or don't know about.

The few basic sorting algorithms are: selection sort, insertion sort, and bubble sort. Then there's slightly faster algorithms like merge sort.

Selection sort selects the smallest element and moves it to the beginning of the list. From my understanding, the big-O of insertion sort is always going to be N-1 because it has to check and compare.

Insertion sort picks an element and moves it if the next element is smaller, the picked element is moved until it's not smaller than the next element it's checking. But...this is kinda where my understanding of insertion sort stops. I should look into it more.

Bubble sort works similarly but it "bubbles" the elements in one way or another, for example in a list with [4,1,3,2,5], bubble sort will first bubble 4 all the way to the correct position, then go back to check from 1,2,3... this is super simple contrived example but it seems like that's the basic concept.

The above three algorithms use basic one check at a time approaches which can be ok for smaller sets of data but as the dataset grows in size, their runtimes can be very slow.

From what I've studied, the next algorithm I'm familiar with is merge sort. Merge sort uses a divide and conquer approach, and the trick up its sleeve is recursion. So it's good to have a grasp on how recursion works before diving into merge sort but simple put it takes the following steps:

1. splits the elements in half until each half only has 2 elements left
2. it sorts the elements
3. merges the sorted arrays

At a high level it seems simple but implementing it can be a bit tricky. First you have to handle the default case so the recursion knows when to end. This can be done by this: if array size is 1, return array. Next, you have to split the array into smaller arrays, so if an array is 5 elements big, you'd split one into 3 elements and the other into 2 elements. Now when it gets to the list with 2 elements, it will split them once more and at this point it will run a separate function that will "merge" these two. And the way it does this is by comparing which of the two single element arrays contains the smaller integer.

Here's a javascript implementation of this:

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}

const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
const sortedArray = mergeSort(unsortedArray);

console.log("Unsorted Array:", unsortedArray);
console.log("Sorted Array:", sortedArray);

Ok so these few I have a basic grasp of but I'm not too familiar with other sorting algorithms.

The following are new to me (from the wiki on sorting algorithms):

• Quicksort
• Heapsort
• Tree sort
• Library sort
• Block sort
• Tournament sort
• Timsort
• Patience sorting
  And a bunch more.

On Wikipedia, there's a nice comparison of different attributes for the algorithms like best, average, and worst runtimes along with memory usage, stability, and the method used for sorting.

For things like merge sort, the runtime the same in all cases which is O(n log n) but space usage is n (which isn't bad, IIUC). But things like Quicksort can be average n log n but worst can be n^2.

Quick sort

This one is a new one to me so I'm going to focus on it a bit because I want to learn about it.
So reading the algorithm details on wikipedia, this is what I found:

1. Because this is a recursive algorithm, when there less than 2 elements, then return.
2. If more than 2 elements, pick an element and call it the pivot.
3. Use two algorithms, one called quicksort and the other called partition, the former being the main function that will insure recursion stops when it needs to, splits the array at the pivot and passes one side of the partitioned array to one quicksort and the other to another quicksort function call.
4. Inside the partition function, the same approach is used as having a pivot and then using that to compare against.

Out of time

I spent way more than 2 hours on this today. I spent close to 3 hours on this and I wasn't able to capture all my thoughts and learnings into one succinct post. I'm happy with this because it forced me to go back and review my fundamental understanding of some basic algorithms.
I think in the future, I'd want to timebox better and stick with it.

Questions for future self

• How is quicksort better or worse compared to merge sort?
• What are some other useful and commonly used sorting algorithms?