Visualize sorting algorithms side by side

A few weeks ago I found out this imgur gallery of sorting algorithms through a reddit post. The patterns which emerged while sorting random data looked very beautiful and amazing with the only catch that they were not interactive. You can not play with them. I decided make them in JavaScript to see what many different sorting algorithms look like, the patterns they create, while also learning them in the process.

In this video you can listen to sound patterns of various alogrithms. Same can be done in JavaScript using its audio api. I added it along with visualization and now you can listen to sorting algorithms :)

Demo

Works on Chrome Desktop and Chrome Mobile

Embeded example

What it looks like

I used CanvasRecorder.js to record these videos.

Bubble Sort is kind of Hello world of sorting algorithms. To perform bubble sort, loop through array while keeping an eye on current and next element and swap these two whenever current one is bigger until you reach the end. Keep repeating this process until no swap is done in a loop.

Cocktail Sort is bubble sort which bounces back and forth instead of going in only one direction. To do this, instead of starting from the beginning on every iteration, start swapping in reverse when you reach the end.

Odd-Even Sort is a modification of bubble sort with two loops, one for even indexes and one for odd.

Insertion Sort bubbles each item back to its correct position: Start from second item, and loop back to first item while swapping where required. Pick next item and repeat til end of array.

Gnome Sort (Stupid Sort) is similar to insertion sort. Unlike insertion sort, which even after correctly positioning the selected item still runs upto first item, skips those comparisons but has to iterate back to next item which needs to be sorted.

These two look exactly same when visualized. You can only see the difference on lower detail levels.

Comb Sort is like bubble sort with varying swap item distance. Bubble sort always swap adjacent items, while Comb Sort starts swapping very distant items and gradually narrows the distance on each iteration. This also increases the number of comparisons on each iteration.

Selection Sort is a simple algorithm. It starts from first item and iterate through remaining list to find a smaller item and, when found, swap with it and move to next item and repeat the process.

Merge Sort is the basic divide and conquer algorithm. It splits an array recursively until it can not be further divided. Sorting happens on the merge step. Splitted arrays are merged in a way so that final array is sorted. This goes on until all pieces are merged together making a sorted array. I splitted the arrays in-place and only created copy of each split to put back in original array.

Parallel Merge Sort is different only in that both recursive split calls are run in parallel instead of one after another. Arrays are drawn from left to right and waves can be seen going because initially there are too many async calls which reduce with each merge.

When compared with normal merge sort, you can see how fast it is

Radix Sort is a weird sorting method. It sorts without doing comparisons. It put items in buckets based on their last digits, then empty the buckets back into the list. This is repeated for the second last digit and so one until the last digit where it will be all sorted. e.g. If largest number in an array has 4 digits, it will iterate only 4 times.

Quicksort is a little different. It puts all smaller and all greater items on left and right of a selected pivot in any order. Start by selecting right most as pivot. Compare with first item, if bigger, move it to right side of pivot by shifting pivot to left. Continue moving right and shifting pivot to left until all bigger items are on its right. Repeat on both sides of pivot.

Comb sort is the smoothest one

What I learned

I learned some algorithms plus a few other things while doing it. setTimeout and setInteral are costly. When used inside a loop, which completes within a millisecond even after doing thousands of swaps, these calls increased the time to ~20ms.

Very first and extremely horrible approach was to store the state of array on each step and play it back on canvas. It used way too much memory to even think about using bigger (greater than 100 elements) array.

Next approach was to only store swap and write operations (only indexes) in the array. Although it didn’t use as much memory, playing back was still very slow.

Then I used async/await and a sleep function which waits on setTimeout. This gave more control over the detail of visualizations and made the code easier to work on. It was still not fast enough. Everything slowed down when I increased the data grid size to around 200 to 300. Another improvement was drawing only what’s changed instead of whole array. That made a huge difference in speed. What did it in the end to display sorting on 512x512 smoothly was rendering on OffscreenCanvas and keep copying back from it on the visible canvas.

What more

More algorithms, plot in time domain to get the pattern in one picture like this