Just Some Thoughts

Stability in Sorting Algorithms

The 10th edition of the ECMA specification of JavaScript required that the Array.sort method be stable. Here I want to have a deeper discussion as to what sorting and stability mean from a formal, mathematical perspective, in addition to discussing the ramifications of the change.

What Defines Sorting

I want to start by really delving into the mathematical definitions underpinning what makes sorting possible, and I will argue that unstable sortings aren't actually sorts on the elements of the array at all (depending on your definition).

The one thing that every sorting requires is a way to determine the order in which to place things. This is accomplished with an ordering.

Ordering

An ordering is a type of mathematical relation defined on some set that satisfies three conditions:

These are the things that define an ordering. However, above, I noted that an ordering must have a condition for equality, which might cause you to ask what equality is. Or maybe it doesn't. Regardless, let's see.

Equivalence

Equality, or equivalence, is also a type of mathematical relation defined on a set. It, like an ordering, is both reflexive (x = x) and transitive (if x = y and y = z, then x = z). However, unlike an ordering, an equivalence relation is symmetric, not antisymmetric.

A relation '=' is symmetric if, for all x and y in the set on which the relation is defined, x = y implies that y = x.

These are all very familiar aspects of equality. It's often the case that things being familiar cause us to scoff at definitions of them, but it is important in math, as well any technical discipline (like computer science), to be as explicit as possible in our definitions, all the way to the most basic things*. This avoids miscommunication and allows us to rigorously define more complex concepts.

And speaking of defining more complex concepts, that's exactly what we are going to do. This whole discussion, recall, is about stability in sorting, a concept that arises from elements being equal. We will find the following definition of an equivalence class useful in this discussion.

Equivalence classes

An equivalence class is a subset of a set on which an equivalence relation is defined such that all elements of that subset are related to each other by the equivalence relation. That was a lot of big words, so let's look at an example.

The equivalence relation '=' is a bit too simple to be an illustrative example, so instead we'll consider a different relation, this time on the integers. We will say n is related to m if they have the same parity (either both odd or both even).

Given this relation, there are two equivalence classes: the even numbers, and the odd numbers. Both of these are subsets of the the original set (the integers) in which every element is related to every other element by the relation, satisfying the definition of equivalence classes.

With these definitions out of the way, we're ready to return to the subject at hand.

The problem with sorting arrays

The particularly attentive might have noticed a certain keyword ever-present in the above definitions. The keyword was set. All of the above definitions were defined on sets, and arrays are not sets. Arrays must order all elements, regardless of whether they are considered equal. This requires a modification in the way we handle sorting them, as two elements of an array can't share an index, and so can't actually be considered equal, in a sense. How we handle this is what will determine whether our sort is stable or not.

In a stable sort we impose an ordering on elements that are equal: the ordering present in the original array. This way we have an ordering for every element, and no desire to assign different elements to the same index. This is not the case in unstable sortings.

In unstable sortings, there is no rule present for assigning two elements that are equal. In the absense of such a rule, there are multiple possibilities for the final ordering. This violates the reflexive property of an ordering, as for some implementation an element might be sorted to index 5, let's say, but with a different implementation it might be sent to 4, yet 5 ≤ 4 is not so. Unstable sorting is thus not a sorting of the elements of the array, but rather a sorting of the equivalence classes present in the array.

Note that I'm talking on an abstract level. Any given implementation of an unstable sorting algorithm is absolutely a sorting on the elements of the array*. It's just that you can define the ordering of stable sorts prior to any implementation, whereas it is the particular implementation of unstable sorting that determines how elements are sorted.

Speaking of implementations, let's actually look at some. We've been very abstract thus far, so now we'll apply our discussion to actual code.

Implementations and Examples

The most popular sorting algorithms are mergesort (stable) and quicksort (unstable).

Mergesort

Here is an implementation of mergesort in JavaScript.

function mergesort(arr) {
  function sort(arr, helper, low, high) {
    if (low < high) {
      let middle = low + ((high - low) >> 1);
      sort(arr, helper, low, middle);
      sort(arr, helper, middle + 1, high);
      merge(arr, helper, low, middle, high)
    }
  }
  sort(arr, [], 0, arr.length - 1)
}

function merge(arr, helper, low, middle, high) {
  for (let i = low; i <= high; i++) helper[i] = arr[i];
  let helpL = low, helpR = middle + 1;
  let current = low;
  while (helpL <= middle && helpR <= high) {
    //   Removing this ↓ '=' sign would cause instability despite still sorting
    if (helper[helpL] <= helper[helpR]) arr[current++] = helper[helpL++];
    else arr[current++] = helper[helpR++];
  }
  let remaining = middle - helpL;
  for (let i = 0; i <= remaining; i++) arr[current + i] = helper[helpL + i]
}

The line below the comment, as the comment indicates, requires the comparison to be '≤' in order to be stable. Switching to a simple '<' would still give a valid sorting algorithm, but it would no longer be stable. As an exercise you might try to convince yourself that this is true.

Quicksort

Here is an implementation of quicksort in JavaScript.

function quicksort(arr) {
  function sort(arr, low, high) {
    let index = partition(arr, low, high);
    if (low < index - 1) sort(arr, low, index - 1);
    if (index < high) sort(arr, index, high);
  }
  sort(arr, 0, arr.length - 1)
}

function partition(arr, low, high) {
  let pivot = arr[low + ((high - low) >> 1)];
  while (low <= high) {
    while (arr[low] < pivot) low++;
    while (pivot< arr[high]) high--;
    if (low <= high) swap(arr, low++, high--); // swap swaps the elements at
  }                                            // indexes low and high in arr
  return low
}

This algorithm is unstable. To see why, we will consider a simple example.

If we change arr[low] < pivot to arr[low] % 7 < pivot % 7, doing like for the comparison on the line below it, and feed in an array like [1,7,8], the result would be [7,8,1], in which the 8 precedes the 1, despite the opposite being true in the original array.

If we made the same change to mergesort and tested the same array, we would get [7,1,8], with the 1 and 8 in their original order.

When to use which

Most of the time the stability of a sort doesn't particularly matter. There are two common misconceptions of when this is the case, however. One is that stability doesn't matter when you're sorting immutable pieces of data, but as we have seen above this isn't accurate.

Another misconception, more common, is that the stability of a sorting doesn't matter when you don't have repeat elements. This, again as we saw above, also isn't the case. The one and only case where the stability of a sorting algorithm truly doesn't matter is when every equivalence class defined by the relation has only one element in it, a cardinality of one as mathemeticians would say.

Avoid the temptation to apply this to mutable elements too hastily, however. If we were to sort the array of arrays [[1],[2],[1]] based off the order of the element each array contained, we run into the danger of thinking that the equivalence classes are {[1]} and {[2]}, but this isn't so. Any two mutable elements are in fact distinct, regardless of their content, and as such the equivalence classes here would be {[1], [1]} and {[2]}, despite the fact that we represent the elements of the first equivalence class in the same way.

Of course, you can use unstable sorts even when equivalence classes have more than one element, as often times you simply don't care about the ordering of equivalent elements. This discussion is aimed at a better understanding of the cases where you do care.

Quicksort is often faster than mergesort and uses less memory, so it is often preferred. This is why the V8 engine used quicksort prior to the recent ECMA specification. Firefox has used mergesort for quite a while, however.

What the Change Means

I would argue this change is for the best. Without specifying an ordering on equivalent elements different browsers would produce different results. If an airline had an online spreadsheet of tickets for flights sorted by time, but then wants to sort them by name of ticketholder, a stable algorithm would keep groups of people with the same name in chronological order, while an unstable algorithm wouldn't. If such a thing were implemented using the Array.sort method, using Firefox would produce a different ordering than in Chrome. That might turn out to be quite a problem.

Of course that developer could implement his own algorithm, but that would require extra work, which no one wants. This change prioritizes the more general use-case, and this way people who demand the most performance can implement their own algorithms, instead of the people who just want their array sorted consistently.

Ultimately what should be taken away from this discussion is that unstable sorts, on an abstract level, are only sorts on the equivalence classes in the array, and as such a distinction between them is relevant whenever the size (cardinality) of equivalence classes is greater than one. It should also always be remembered than any two elements that are mutable are distinct.

This gives sufficient criteria for determining the type of sort desired in any given circumstance. Again, I would say that the change in the specification is a good one because the result of a stable sorting algorithm will always be the same with the same input. Unstable sorts certainly have their place, but part of determining their place is to know when not to use them. I hope this discussion has been helpful in determining when exactly that is.