Interview Kickstart has enabled over 3500 engineers to uplevel.
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:
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.
On the basis of stability, a sorting algorithm can be stable or unstable:
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.
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.
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.
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.
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:
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).
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