Introduction to sorting algorithms in JavaScript

Now that we’ve covered basic data structures, it’s time to apply those structures to one of the most basic applications of algorithms: sorting. Sorting, as the name implies, organizes and divides objects for us in order to make them easier to find and use.

This article is part of the Data Structures and Algorithms Series following the course The Analysis of Algorithms. If you missed the previous article, check that out first as well as a copy of The Algorithm Design Manual.

Over the next several articles in this series, we are going to implement many of these basic sorting algorithms in JavaScript so you can compare and contrast the approaches and even find which are used in the JavaScript language today.

Answers to the Daily Problem

This round our Daily Problem is back to coming directly from the book, practice problem 4-3:

Take a sequence of 2n real numbers as input. Design an O(n log n) algorithm that partitions the numbers into n pairs, with the property that the partition minimizes the maximum sum of a pair. For example, say we are given the numbers (1,3,5,9). The possible partitions are ((1,3),(5,9)), ((1,5),(3,9)), and ((1,9),(3,5)). The pair sums for these partitions are (4,14), (6,12), and (10,8). Thus the third partition has 10 as its maximum sum, which is the minimum over the three partitions.

There’s a lot of words here but we can reason about this another way: the pattern here is to minimize the largest sum is pairing the maximum number with the minimum number, and working inward.

We first need to sort (which takes n log n) the numbers, and then pair them off by taking the maximum() and the minimum() number from the set, plucking them out of the old set and placing them into a new set. Finally, we take the largest number from those pairs and that’s the maximum sum that is the minimum across all possible permutations of the problem. In pseudocode, it looks something like this:

function minimumMaxSum(set) {
  let sortedSet = set.sort();
  let pairs = [];

  while (sortedSet) {
    let maximum = sortedSet.maximum();
    let minimum = sortedSet.minimum();
    pairs.push(maximum + minimum);
    sortedSet.remove(maximum);
    sortedSet.remove(minimum);
  }

  return pairs.maximum();
}

Applications of sorting

If you’re wondering why sorting gets so much attention in interviews, it’s because sorting is so important and so common. In fact, it is reported that nearly a quarter of all computational time is spent in just sorting data. Because it’s so common, we have developed dozens of algorithms to tackle this problem, and is in fact one of the most studied problems in computer science. Here are just a few of the common use cases for sorting:

Searching: If you want to find stuff, it’s going to be way easier to find stuff if it’s organized. Can you imagine searching for books in a library if everyone just stuffed their books in there arbitrarily?
Frequency / Uniqueness: Remember things like mean, median, and mode from math class? It’s much easier to find the mean and median if you know they are roughly in the middle of your set. Similarly, the mode will always be grouped together in the largest group of a set; all made easier by sorting.
Selection: Like search, picking something out of a set is much easier when it’s in a group of sorted items. Otherwise, the thing you want to pick is in a random group and may take longer to find.

Approaches to sorting

When you think of sorting items, what comes to mind? Probably something like largest to smallest (or vice versa), and probably involving numbers. But lots of data can be sorted in lots of different ways, so before we dive into sorting algorithms it’s important to remember that this is not the only way to sort. Here are a few more examples to consider when using sorting algorithms:

By key/record: Just because we have the largest/smallest piece of data doesn’t mean it is special. Sometimes it has to do with when/where that data was entered. When we enter data into a database with a unique incremental ID, we can sort by created-at date using the key of that record.
By alphabetical ordering: Numbers increase and decrease, but so do letters based on their ordering in an alphabet. Even though there is no mathematical basis for A to be “less than” Z, there is a semantic and contextual basis.
By frequency: Even if something isn’t the newest or the largest, we may want to have the most popular/frequent data at the top to show to customers. Grouping by frequency and sorting on that can also be very important in picking out outliers.

Just like applications, the approaches to sorting are also numerous. What’s important is not that this list is exhaustive, but that it is a starting point for thinking about sorting as a fundamental activity of computer programming. Whether or not you’re a web programmer or an AI programmer, you will have to sort some data while doing your job. Knowing how that works under the hood is advantageous, particularly if you’re needing to optimize your programs for performance.

One caveat: just because you should learn how this works doesn’t mean you should implement your own sorting algorithms in a professional setting.

This is important because while programming interviews may ask you to implement algorithms to commonly-solved problems, that doesn’t mean you should actually use them in the real world. What is important is that you know how it works, not that you need this in your arsenal of tools to implement.

Next time, we’ll look at one of these high performers that uses priority queues, a special variant on queues that we’ll explore in-depth while we spell out our first sorting algorithm.

Next Daily Problem

This one is pretty straightforward question, sort of something like you’d see out of a programming interview!

Give an efficient algorithm to determine whether two sets (of size m and n) are disjoint. Analyze the complexity of your algorithm in terms of m and n. Be sure to consider the case where m is substantially smaller than n.

Think you have one in mind? Throw it up on a gist and send it to me on Twitter!

Liked this post? You'll probably also like:

Get the FREE UI crash course

Sign up for our newsletter and receive a free UI crash course to help you build beautiful applications without needing a design background. Just enter your email below and you'll get a download link instantly.