How Sorting Works Under The Hood (QuickSort)

Ever wonder what happens when you do sort() on an array?

In most languages, it uses an algorithm called QuickSort. Here's how it works in a nutshell.

Assume you have a bunch of cards you want to sort. Here's some IRL cards in an arbitrary order.

We pick what's called a "pivot". Then group the rest of the cards based on if they are greater than or less than the pivot. I'll use index 0 as my pivot in this case.

Now we have two nice stacks of cards that are less than (or equal to) and greater than the pivot, but those stacks themselves are not sorted.

Fine, we'll just do the same thing on the cards therein.

We just keep doing this on the progressively smaller stacks until we get to n = 1 for each stack.

Finally, the cards are sorted and we can just merge them back together.

Let's take a look at some code examples. These are not the most efficient implementations BTW, we are optimizing for simplicity here.

function quicksort<T>(array: T[], on: (data: T) => number): T[] {
    if (array.length <= 1) return array;
    
    const pivot = array[0];
    const remaining = array.slice(1, array.length);
    
    const left = remaining.filter(data => on(data) <= on(pivot));
    const right = remaining.filter(data => on(data) > on(pivot));
    
    return [...quicksort(left, on), pivot, ...quicksort(right, on)];
}

You can see it handling the base case, selecting the pivot, dividing into the sub-arrays, and finally merging them back together.

Another tangential thing, you can see we have a function parameter on that references type T and returns a number. Therefore, we can use our quicksort function on whatever data we want, interface or type notwithstanding.

For our cards, we could do something like this.

interface Card {
    suite: Suite;
    number: number;
}

const cards: Card[] = [
    { suite: Suite.clubs, number: 5 },
    { suite: Suite.spades, number: 4 },
    { suite: Suite.diamonds, number: 6 },
    { suite: Suite.diamonds, number: 11 },
    { suite: Suite.spades, number: 10 },
    { suite: Suite.clubs, number: 7 },
    { suite: Suite.clubs, number: 3 }
];

const sorted = quicksort(cards, card => card.number);
console.log(sorted);