What is Stable sort?

A sort that keeps elements with equal keys in their original relative order. Bubble sort, insertion sort and merge sort are stable, while selection sort, quicksort and heapsort are generally not. Stability is needed when sorting by several keys in turn.

Japanese name: 安定ソート

Stable sort appears in 1 practice question across 1 topic, including Data Structures and Algorithms.

Field: Data Structures and Algorithms

Try it: questions about Stable sort

The (name, score) records (A, 80), (B, 70), (C, 80), (D, 70) are in this order. If they are sorted by score in ascending order with a stable sort, in what order do the names appear?

AB, D, A, C
BD, B, A, C
CB, D, C, A

Show answer and explanation

Answer: A. B, D, A, C

A stable sort keeps elements with the same key (here, the score) in their original relative order. B and D, both with 70, stay in the order B, D, and A and C, both with 80, stay in the order A, C, giving B, D, A, C. Bubble sort, insertion sort and merge sort are stable, while selection sort, quicksort and heapsort are generally not. With a stable sort you can sort by several keys, for example sorting by name first and then by score.

Stable sort in the explanations

A stable sort keeps elements with the same key (here, the score) in their original relative order.
The (name, score) records (A, 80), (B, 70), (C, 80), (D, 70…