Stable Sort

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

What's next?

If you're ready to start applying these concepts to some problems, check out our mock coding interview questions.

They mimic a real interview by offering hints when you're stuck or you're missing an optimization.

Try some questions now

. . .