Software engineers learning sorting algorithms for their technical interview prep will come across phrases such as “this algorithm is stable,” and should have a clear idea of what that means and why it matters. 

For any role, like software developer or coding engineer, in-depth knowledge of implementing sorting algorithms comes in handy, and an understanding of stability in sorting algorithms aids the development of that skill. So let’s get right into it!

In this article, we will learn:

• What Is Stability in Sorting Algorithms?
• Difference Between Stable and Unstable Sorting Algorithm
• Stable vs. Unstable Algorithm: Example
• When Does Stability Matter?
• In-Place Unstable Sorting Algorithms
• Examples of Coding Interview Questions on Sorting Stability
• FAQs on Sorting Stability
  

What Is Stability in Sorting Algorithms?

The concept of stability in sorting algorithms is concerned with how the sorting algorithm treats elements with the same keys. Here, “the key” is that part of the element on the basis on which the sorting is done. The key may or may not be the entire element. 

A sorting algorithm is said to be stable if in case of a tie on the basis of the key value, the relative order of the elements in the original input is maintained after sorting as well. In other words, a stable sorting algorithm preserves the relative order of elements with equal keys. 

Difference Between Stable and Unstable Sorting Algorithms

On the basis of stability, a sorting algorithm can be stable or unstable:

• Stable sorting algorithm: It preserves the relative order of elements with equal keys. These elements are referred to as stable elements. Counting sort, bubble sort, insertion sort, radix sort, merge sort, and tim sort are all stable.
• Unstable sorting algorithm: This type of algorithm typically does not guarantee to preserve the relative order of elements with equal keys. This means that the algorithm is such that the typical implementation of it does not set out to preserve the relative order, but it may happen to be preserved in some cases by chance. Such an occurrence is unlikely, but not impossible. Heap sort, selection sort, and quicksort are examples of unstable algorithms.
  

Some algorithms are stable or unstable depending on the stability of the underlying subroutine sort used in their implementation. For example, bucket sort is stable if the underlying sorting subroutine it uses is stable. 

Additionally, some unstable sorting algorithms can be made stable by doing some tradeoffs and alterations. For example, we can make quicksort stable by making the tradeoff of using extra space.

In conclusion, the difference between a stable and unstable sorting algorithm lies in whether the algorithm works in a way that guarantees that the relative order of elements with equal keys will be preserved. 

Let’s understand this difference better with the help of an example.

Stable vs. Unstable Algorithm: Example

Input: Key-value pairs to be sorted on the basis of the key (score). They are already stored in alphabetical order of names in the input.

‍Stable Sort: The names are sorted on the basis of the score —  when the score is the same, the relative order of names is preserved. This means that the names of people with the same score will be in alphabetical order if we use a stable sorting algorithm.

Unstable Sort: Here too, the names are sorted on the basis of score. However, for people with equal scores, the relative order of names is different than it is in the alphabetically sorted input. This means that the names of people with the same score will, barring coincidence, NOT be in alphabetical order if we use an unstable sorting algorithm.

When Does Stability Matter?

The example above gives a glimpse of when such a differentiation based on stability may be useful. In essence, this differentiation is useful if keys with the same value exist, as in the above example. 

If the keys are all different, or if equal elements are indistinguishable, such as when the entire element is the key, the differentiation based on stability is irrelevant.

In-Place Unstable Sorting Algorithms

A sorting algorithm is said to be “in-place” if it does not use extra space for operations on the input. It may or may not require some small, non-constant extra space for manipulating the input. 

Some in-place unstable sorting algorithms can be made stable by altering their implementation to use extra space. If you use this kind of alteration, the algorithm’s implementation will become stable, but it will no longer be in-place.

Examples of Coding Interview Questions on Sorting Stability

If you’re preparing for a coding interview, you can expect questions or problems based on stability. Here are a few examples that you can use in your interview prep:

1. Can quicksort be made stable? What changes would need to be made in its implementation to achieve that? (The same question can be asked for other unstable sorting algorithms)
2. Can any unstable sorting algorithm be altered to become stable? If so, how?
3. What is the use of differentiating algorithms on the basis of stability?
4. When is it definitely unnecessary to look at the nature of stability of a sorting algorithm?
5. What are some stable sorting techniques? If you want to sort in-place, which ones would you consider choosing from?
6. What properties of sorting algorithms are most likely to get affected when a typically unstable sorting algorithm is implemented to be stable?

FAQs on Sorting Stability

Question 1: In what cases should we prefer using stable sorting algorithms?

We should prefer using stable sorting algorithms when equal keys exist, and we want to layer multiple criteria on the basis of which we want the elements to be ordered. In other words, if we want the ordering within elements having equal keys to be on the basis of some other criterion as well, we should prefer stable sorting algorithms. This will help to get an input that is sorted by keys, and in case the keys are equal, the other criterion is the basis of ordering.

Question 2: If an unstable sorting algorithm happens to preserve the relative order in a particular example, is it said to be stable?

Unless the typical implementation of the unstable sorting algorithm is adjusted such that it guarantees a stably sorted result, just the mere coincidence of it giving an output that happens to preserve relative order does not mean the algorithm is stable in that case. It would be more appropriate to just say that the relative order is preserved in that case, instead of commenting on the nature of the algorithm, since the “stable sort” behavior is the result of the example, not the algorithm.

Question 3: How can you convert an unstable sorting algorithm into a stable sorting algorithm?

An unstable sorting algorithm can be converted into a stable one by making some algorithm-specific modifications in the implementation. For example, in some cases, it can be achieved by altering its implementation to include only stable subroutine sorts (works for bucket sort) and/or using extra space (works for quicksort).

Are You Ready to Nail Your Next Coding Interview?

Sorting algorithms interview questions feature in almost every coding interview for software developers. If you’re looking for guidance and help to nail these questions and more, sign up for our free webinar.

---------
Article contributed by Tanya Shrivastava