Interview Cake
A stable sorting algorithm ensures that items that are equal to each other aren't reordered during the sorting process.
For instance, suppose we're sorting a list of computer science majors by their grade point average.
[('Mia', 3.9), ('Andrey', 3.2), ('Yvette', 3.9), ('Theo', 3.5), ('Charlie', 2.7)]
A stable sort will put Mia before Yvette in the sorted list, since Mia is before Yvette in the input.
[('Charlie', 2.7), ('Andrey', 3.2), ('Theo', 3.5), ('Mia', 3.9), ('Yvette', 3.9)]
An unstable sort doesn't offer any guarantees about Mia appearing before Yvette. So it's output might look like this:
[('Charlie', 2.7), ('Andrey', 3.2), ('Theo', 3.5), ('Yvette', 3.9), ('Mia', 3.9)]
These sorting algorithms are usually stable:
- counting sort
- merge sort
- insertion sort
These sorting algorithms are usually not stable:
- quicksort
- heapsort
- selection sort
Interview coming up?
Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.
No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.
No spam. One-click unsubscribe whenever.
You're in! Head over to your email inbox right now to read day one!
