Sorting algorithms 101

Stable vs unstable sorting

Before we dive in, a quick note on stable and unstable sorting. In the sorting world, we’ll often come up against multiple instances of the same value. In the array [1, 5, 7, 5, 3, 5] for example, we’ll encounter 5 three times, and so our algorithm may be doing wasted work on comparing such values together and (potentially) rearranging them.

1. Quick sort

This algorithm relies on a simple premise; we sort a single value in an array of data, and then another one, and another one, until we sort the entire array. Each time we do this, we mark the now sorted point as a “pivot”, move all numbers lower than it to its left, move all numbers higher than it to its right, and then repeat the algorithm on either side of that point.

2. Merge sort

Here we split our to-be-sorted data into 2, right down the middle. Then, we run each half through the merge-sorting algorithm again, where it will be split recursively until we have just 2 pieces of data (1 on each side). From there, we re-combine each side in sorted order, until we eventually return to the top level with a sorted dataset.

3. Bucket sort

In this algorithm, we divide our dataset into ordered buckets, sort each bucket, and then concatenate the buckets to give us a fully sorted set. This can make for a very elegant solution, especially if we pick the right number of buckets, however just like with quick-sort, picking the wrong number of buckets can slow things down significantly.

4. Bubble sort

In this sorting algorithm, we are simply comparing values with their immediate neighbours. The way we do this is that we loop through the dataset, and we compare the value at i with the value at i + 1 . If i is higher, than we swap the two values and increment i. After the first run, we will have identified the biggest value in the data, and moved it all the way to the right. Now on the next run, we will identify the second biggest value, and can ignore the already correctly placed value at the end of the array.

5. Insertion sort

Much like with bubble sort, insertion sort loops through the values of an array, but this time it compares it with the number to its left. If the left-hand number is lower, then those two values are sorted (for now), and we move onto the next one. Once we find a value that is not lower than the one to its left, we loop through the values on its left until we can find (and place it in) its correct position.

And beyond

There are a huge number of additional sorting algorithms out there, and I hope to add more to this article in the future.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Duncan McArdle

Duncan McArdle

110 Followers

Full-stack software developer from the UK, author of the Aftermath book series, full time tech-nerd.