# Sorting Out The Basics Behind Sorting Algorithms

### Vaidehi Joshi Sep 23 '17

Weâve covered a whole array (pun totally intended) of data structures in this series thus far, and so far, Iâve really enjoyed exploring all the different ways that programmers and the software that they build lean on those structures to help them solve interesting problems. But todayâs post is special, because weâre finally going to get into some of the more science-heavy stuff (if we can even call it that) that makes up the world of computerÂ science.

Okay, I wonât subject you to a big build up; letâs get right to it. Weâre going to finally get into *algorithms*âââhooray! Over the next few weeks, Iâll be diving into some of the most common and widely-referenced algorithms that are used in computerÂ science.

If you donât come from a computer science background (or if youâre fairly new to programming), the prospect of an algorithm deep-dive might sound pretty bad. Or perhaps outright terrifying. But fear notâââweâll get through this together, and come out of the whole experience as algorithm experts! So letâs start with the very basic stuff first. Namely: what even *is* an algorithm? Weâre going to learn a lot about them, so we should probably have that definition straight in our heads,Â right?

Well, as it turns out, an algorithm is a really fancy name with a bad rap. Theyâre not nearly as scary as they sound. An ** algorithm** is just fancy term for a set of instructions of what a program should do, and how it should do it. In other words: itâs nothing more than

*a manual for your code*. Thatâs it. (Really!) Some of the most-referenced algorithms in the world of software are generally a subset of

*sorting algorithms*, or algorithms that provide a set of instructions for how a program or system should go about organizing a set ofÂ data.

### Why sort oneselfÂ out?

Before we can get into the different ways that algorithms can sort data, itâs important for us to have a strong grasp on what sorting is, exactly, in the context of computer science, and why itâs so important.

Weâve all had to deal with some variation of sorting different items in our own, everyday lives. For example, I moved recently, and even though I think I did a pretty good job of packing all my stuff up, there were a lot of things that were fairly disorganized. I had a bunch of papers and writing in the form of a manuscript that I had tossed into moving box in a hurry. Lo and behold, when it came time to unpack, everything was a total mess, and all the pages were disorganized, and it was pretty terrible. I had to sort them by page number manually in the process of unpacking them. If you read enough about sorting algorithms, youâll notice that sorting a deck of cards, sorting books, or sorting a collection of numbers are all commonplace examples of sorting algorithm implementations.

These very examples are extensions of what happens in our code and our applications all of the time! Sorting is particularly helpful in the context of computer science for twoÂ reasons:

- From a strictly human-friendly perspective, it makes a single dataset a whole lot easier toÂ read.
- It makes it easier to implement search algorithms in order to find or retrieve an item from the entireÂ dataset.

In my example, without having sorted all the pages in my manuscript, you can imagine how painful of an experience it would be to try and find a single page in a mixed-up pile of 200Â pages.

So, I guess sorting makes sense on a practical, *human* level. But why do computers care about sorting? They can do things pretty fast, right? They donât need things to be as easy-to-read the way that people do. What good does sorting do forÂ them?

Well, from a computer science perspective, sorting plays a particularly important role because the set of data that a computer, a program, or an application has to search through can oftentimes be *massive*. Like, beyond what most human beings can really fathom searching through kind of massive! Weâll come back to this in aÂ moment.

First, letâs figure out what exactly we *mean* when we talk about sorting in the context of computer science. ** Sorting** is the organizing of a set of a similar items in a collection by some property. There are two important things to noteÂ here:

- We can sort a collection of items in either increasing or decreasing order by any one property, and that property by can really be
*anything*. By size, lexicographical (alphabetical) order, numerical order, date, timeâââyou nameÂ it! - We can only sort a dataset where the items are
*homogeneous*, or are of the same type. In other words, we couldnât sort a dataset with both words and numbers, because that dataset doesnât have a shared property that we could actually*sortÂ by*.

In the example above, there are two homogeneous lists that we have sorted: list_one and list_two. All of the items are of similar types, and weâre sorting them in increasing order. Itâs also worth mentioning that the sorted versions of these lists (list_one_sorted and list_two_sorted, respectively) are ** permutations** , or reorderings, of their original, unsortedÂ lists.

Okay, now that we have the definitions and rules out of the way, letâs come to the most important question: how do computers *leverage* sorting? Why are sorted things good? Similar to how sorted data is more readable for humans, sorted data also makes things a lot simpler for machines, too.

Letâs take a look at what life would look like without sorting. Spoiler alert: it seems prettyÂ bad.

In the example above, we have a tiny list of unsorted numbers. Imagine that we wanted to find the number 33, but didnât know where it was. Or, in an even more terrible scenario: imagine we want to find a number that isnât even *in* the list! In the worst case, weâd have to look through every single one of the numbers, until we got to the end, and realized that the number wasnât even in the list! In other words, it would take *linear* time. Using our example dataset, the amount of time it would take us to look through all of the numbers would be prettyÂ small.

But what if it was 100 million numbers? Or 1Â billion?

Okay, donât panic! Weâre not going to try to sort through 100 million numbers, donât worry. Letâs look at what finding one number in that same dataset would look like when it wasÂ sorted.

If the example above looks familiar to you, thatâs because itâs our good old friend, binary search! Finding one number in the exact same example dataset (even if the number doesnât even exist in the list) never takes more than *logarithmic* time. Hopefully, you remember that this is all because binary search is implemented by eliminating half of the possible search results with each comparison.

This is exactly how our programs leverage sorting! Binary search is a great way to insert, delete, or read and retrieve information from a large dataset. And even if the dataset was 100 million, this would be easy to do for our code to search throughâââas long as the list wasÂ sorted.

### All sorts of classifications

Now that weâre all on board with sorting as a concept, itâs time to break down the different types of sorting algorithms that are commonlyÂ used.

There are many ways to classify a sorting algorithm, but weâll focus on just six of them: time complexity, space complexity (or memory usage), stability, internal or external, recursive or non-recursive, comparison sort or non-comparison sort. These classifications end up being important factors for programmers when they are writing a sorting algorithm or choosing which one to implement.

It all comes back to a theme that weâre already familiar with at this point in the series: different tools each have their own benefits and drawbacks. As we delve into some common algorithms over the next few weeks, weâll use these classifications to help us decide what those benefits and drawbacks are for any given sorting algorithmsâââand when that algorithm might be helpful (or maybe not so helpful!).

Letâs take a look at each of these classifications in moreÂ detail:

#### 1. Time complexity

The easiest way to classify an algorithm is by *time complexity*, or by how much relative time it takes to run the algorithm given a different inputÂ size.

Since weâre already pretty familiar with the concept of time complexity (or, *Big O* as we often refer to it), this is how weâll break down all of our algorithms as we start learning about them in moreÂ detail.

#### 2. Space complexity/memory usage

Different algorithms requires a different amount of space, depending on their space complexity. Another way of thinking about *space complexity* in the context of sorting algorithms is by answering the question: *How much memory will this algorithm need toÂ run?*

There are two types of classifications for the space complexity of an algorithm: *in-place* or *out-of-place*.

An ** in-place** algorithm is one that operates directly on the inputted data. The danger with this is that the data is getting completely transformed in the process of transforming it, which means that the original dataset is effectively being destroyed! However, it is more space-efficient, because the algorithm only needs a tiny bit of extra space in memoryâââusually a constant amount of space, or

*O(1)*âââwhich can be helpful if you donât have enough memory toÂ spare.

In contrast, ** out-of-place** algorithms donât operate directly on the original dataset; instead, the make a new copy, and perform the sorting on the copied data. This can be safer, but the drawback is that the algorithmâs memory usage grows with inputÂ size.

#### 3. Stability

Oftentimes, a single dataset will have more than one element that has the same âsort keyâ; in other words, multiple items in a list could be considered equal in the way that they could beÂ sorted.

In the example shown here, there are two number 4âs, one of which is green, and the other which isÂ red.

There are two ways that this list could be sorted, given the fact that there are two elements that could be sorted âequallyâ: the green 4 could come first, the way that it did in the original list, or the red 4 could be sortedÂ first.

This is exactly what defines the ** stability** of a sorting algorithm.

A ** stable** algorithm is one that preserves the relative order of the elements; if the keys are the same, we can guarantee that the elements will be ordered in the same way in the list as they appeared before they were sorted. On the other hand, an

**algorithm is one where there is no guarantee that, if two items are found to have the same sort key, that their relative order will be preserved.**

*unstable*#### 4. Internal vs.Â external

Because our machines can sort through large datasets fairly easily, itâs common to have some applications that have to sort through *huge* collections of data. In some cases, this can actually amount to more data than can be maintained in the machineâs main memory (orÂ *RAM*).

The way that an algorithm has to store data while its sorting through records is yet another way that we can classify sorting algorithms.

If all of the data that needs to be sorted can be kept in main memory, the algorithm is an ** internal** sorting algorithm. However, if the records have to be stored outside of main memory âin other words, stored in external memory, in either a disk or a tapeâââthe algorithm is referred to as an

**sorting algorithm.**

*external*#### 5. Recursive or non-recursive

Some algorithms do their sorting by dividing and conquering: that is to say, the split up a large dataset into smaller inputs, and then recursively call a sort function upon all of those smaller inputs. This is referred to as a ** recursive** sorting algorithm.

In contrast, a ** non-recursive** sorting algorithm isâââyou guessed itâââone that doesnât implement recursion! This is to say, they donât sort through a smaller subset by calling the same function upon those smallerÂ inputs.

Itâs worth mentioning that most algorithms donât have to be implemented *recursively*; they can be written and implemented iteratively. But whether or not a sorting algorithm is recursive or not ends up being an easy way of classifying one set of algorithms fromÂ another.

#### 6. Comparison sort

Finally, itâs possible to classify a sorting algorithm based on *how* it actually does the job of sorting elements.

Any sorting algorithm that compares two itemsâââor a *pairâââ_at a time in the process of sorting through a larger dataset is referred to as a **_comparison sort***. This subset of algorithms use some type of *comparator* (for example: >= or <=) to determine which of any two elements should be sortedÂ first.

Sorting algorithms that do *not* use any type of comparators to do their sorting are referred to as ** non-comparison sorts**.

For our purposes, nearly all of the algorithms weâll be looking at in this series will be classified as comparison sorts. However, itâs important to remember that not all sorting algorithms require a comparator to defining the ordering and sorting of aÂ dataset!

### Sorting, sorting, everywhere youÂ look!

Okay, weâve exhausted our list of classifications. Hopefully, by now, you can see that sorting algorithms are a *big deal* in computer science! People have spent a huge portion of their careers researching and writing about sorting algorithms! And thereâs a good reason forÂ that.

Sorted data powers (almost) *everything*. Think about it: whenever you interact with a web or mobile application, you can sort a large set of data by some property. Databases also have sort and search through huge sets of data, using something called Btrees. They sort through so much data that we, as humans, canât even wrap our headsÂ around!

We already know about binary search and how often it is used, and how powerful it is. Guess what? Sorted data is a prerequisite forÂ that!

But on a broader level, sorting algorithms are also used in statistics, in order to determine the median of a dataset for example, or in order to find statistical outliers! Sorting algorithms are also used for load balancing on your own individual machine, and is particularly helpful when it comes to processing large amounts of data on multiple processors.

Over the next few weeks, weâll start to see more of just *how* crucial sorting algorithms are for computer science. There are quite a few different sorting algorithms, but weâll cover some of the most commonÂ ones:

Next week, weâll try our hand at actually applying a couple of these sorting algorithms to a real-life problem and start exploring a few of these sorts in more depth. Maybe by the time we get to the end of this algorithm deep dive, youâll change the way that *you* sort things in your own life. Or perhaps youâll just never want to hear about sorting anything, ever again. Iâm going to go out on a limb and say that thereâs a 50/50 chance of either one of those happening.

### Resources

There are tons of papers and entire PhD *dissertations* out there in the wild about sorting algorithms: which ones are best, which ones are efficient, and how to rank and classify them by different categories. You could probably spend years simply reading and learning about them all. Or, you can also just check out these resources if youâre looking for an easy place toÂ start!

- Non-Comparison Based Sorting Algorithms, Professor Ananda Gunawardena
- Data StructureâââSorting Techniques, TutorialsPoint
- Sorting Algorithms, Professor Victor S.Â Adamchik
- Sorting AlgorithmsâââStability, University of Illinois at Chicago, Department of Mathematics, Statistics, and ComputerÂ Science
- Sorting Applications, Professors Robert Sedgewick & KevinÂ Wayne
- Introduction to sorting algorithms, mycodeschool

*This post was originally published on medium.com*

There is something weirdly satisfying about this handwritten notes. And they're really helpful too!

I absolutely love these articles, especially as a visual learner. Incredibly valuable and helpful material, doubly-so because I've never taken any CS courses -- thank you!

That's awesome! Glad to hear that it's helpful. I'm a visual learner too, and have to write everything down in order to

reallylearn it.Nice article. Thanks

Amazing article! That kind of theory is something that

everyprogrammer must know, and the way you lay it out is exceptional.Also, kudos for the pretty drawings :)

Great article!

I

reallylike this one. Vaidehi, you are consistently helping me drop some of my FOMO of dropping out of the computer science program. đHahaha, thanks! I suffer from continual bouts of computer science FOMO myself. â€ïž

Great article!!! Thanks!