Sorting

There are many, many sorting algorithms, each with its own advantages. It’s important to keep the algorithmic differences along with the properties of each separate so you use the correct one depending on the circumstances.

Insertion Sort

Description

How does insertion sort work? Imagine you’re playing Bridge, and everyone starts out with 13 cards in their hand. Ideally, you’d like to sort it. How do you go about doing so? If you’re like me, you start with one of the two ends of your hand. Let’s say you start with the left side.

The first card is in place. You look at the second card. Is it smaller or bigger than the first card? If it’s smaller, you move it to the left of the first card; otherwise, you let it be in place. What about the third card? You insert it somewhere inside the first two cards, or on either edge.

Like this, you maintain a section of cards that are sorted relative to each other, and another section of cards that aren’t sorted. By the time you get to the end of the hand, you’ve sorted all the cards.

Use-case

Why does everyone use insertion sort for sorting a hand of cards? Because insertion sort is incredibly fast on a small input size. It’s actually the fastest for very small inputs. With a small number, it’s obvious to see what the smallest is and where it should go. In addition, it requires no extra memory. Of course, this simple algorithm balloons in cost relatively quickly, and for anything smaller than a trivial problem, it becomes horribly inefficient.

Visualization

From Wikipedia.

The sorted subarray that is being maintained is everything with black outlines around it. If it doesn’t have the black outlines, then it hasn’t been considered yet. Notice that every new element is inserted inside the sorted subarray so that it keeps growing. By the end, everything is inside the sorted subarray.

Selection Sort

Description

Selection sort is in many ways the opposite of insertion sort. Rather than inserting a card into a sorted pile, you are selecting the next element amongst the entire pile.

Imagine you now have my job and are a CS1 TA. Your job is to grade the exams and present them in sorted order by grade to Professor Farid. You decide to employ selection sort because it’s late, you’re sleepy, and selection sort requires very little brainwork. So little, in fact, that you could do it in your sleep.

You choose the lowest scoring exam of the entire class and put it in the bottom. Ignoring the bottom-most exam, you choose the next lowest score of the entire class. That is, you go through the entire pile and find the lowest score.

Contrast this with insertion sort where you always choose the next one in the pile and search through the sorted pile to insert it in the right place. Here, you’re guaranteeing the location it will be selected into and instead searching for what to select.

Use-case

Like insertion sort, this is best used for very small input sizes. It requires no extra memory and is quite fast for small input cases. Unfortunately, it is quite foolish to attempt using this algorithm for larger inputs.

Visualization

Notice that the current minimum has to be stored so that it can be swapped with.

Quicksort

Description

Quicksort can be done either recursively or iteratively. We’ll explain it recursively here. It’s done following these simple steps:

  1. Pick a pivot – usually you pick it such that it’s one of the cards on either end. For this example, let’s go with the right-most end (the last element).

  2. Make everything smaller than the pivot to the left of the pivot, and everything larger than the pivot to the right of the pivot.

How would you do this? It’s up to you. Usually it’s done through a nice series of swaps where you switch elements.

  1. If you’ve done steps 1 and 2, you are guaranteed that the pivot is in the right place. But everything to the left of the pivot, even though it’s all smaller than the pivot, is not sorted. Same for everything to the right of the pivot. So recurse! Call quicksort recursively on the left and right sides of the list.

Use-case

Quicksort is best used for medium to large inputs. It’s much faster than selection or insertion sort for these numbers and is quite a bit speedier than merge sort for medium sized inputs as well. Remember that we mean medium in terms of computer standards (hundreds of thousands, let’s say) and not by human standards.

Visualization

An example of Quicksort from Wikipedia.

The pivot chosen is always highlighted in red. Notice that in this particular algorithm, they move the pivot into position once all the others have been sorted. When you choose to move the pivot does not matter, so long as by the time the sorting is done, everything to the left of the pivot is smaller, and everything to the right is bigger.

Merge Sort

Description

Merge sort is explained best when it’s recursive.

Let’s say you have an array of 8 numbers, 1 through 8. You want to use merge sort. First, keep dividing the array in half until you get arrays of length 2. This will be the base case.

Initial condition

[6, 5, 3, 1, 8, 7, 2, 4]

Then, we divide the array in half, giving us two arrays.

[6, 5, 3, 1] [8, 7, 2, 4]

Keep going until we get arrays of length 2, which is the base case.

[6, 5] [3, 1] [8, 7] [2, 4]

Great, now we’ve hit the base case! Now we sort each of the small arrays – the array is either sorted or we simply swap the elements because there are only two of them.

[5, 6] [1, 3] [7, 8] [2, 4]

Now we have many small base case arrays of length 2. Now we combine, or merge them. How do we merge them? We only merge arrays of the same length that are “close to” each other. So we’ll merge the array [5, 6] with the array [1, 3], and similarly we’ll merge [7, 8] with [2, 4].

The merging process isn’t too complicated. Keep drawing the smallest element into this new array we create. When we merge them, we get two larger arrays.

[1, 3, 5, 6] [2, 4, 7, 8]

Now we keep merging the larger arrays until we get a single, sorted array. This last merging produces the correct result.

[1, 2, 3, 4, 5, 6, 7, 8]

Use-case

Merge sort is meant for large input sizes. It is the absolute fastest, even faster than quicksort, for the very large inputs and will dominate all else. One thing to watch out for is space. Often times, merge sort is implemented recursively, and for large input sizes, stack overflow errors may often occur. An iterative solution may be used to get around this, or other recursive tricks.

Visualization

The Wikipedia visualization is spot on. Note that in the Wikipedia illustration, the base case is actually set to 1 instead of 2. It doesn’t matter which you choose.

Summary

Algorithm Worst Time Best Time Average Time Space
Selection Sort O(n^2) O(n^2) O(n^2) O(1)
Insertion Sort O(n^2) O(n^2) O(n^2) O(1)
Quicksort O(n^2) O(n•log(n)) O(n•log(n)) O(1)
Merge Sort O(n•log(n)) O(n•log(n)) O(n•log(n)) O(n)