stable sort
A sort that keeps items with equal keys in the same relative order they had before sorting.
In more detail
Stability lets you sort by several keys in passes: sort by the secondary key first, then stably by the primary key. Merge sort, insertion sort and Python's sorted() are stable; quicksort and heap sort usually are not.
Related terms
- sorted() and list.sort() — Python's built-in sorts: sorted() returns a new sorted list from any iterable, and list.sort() sorts a list in place.
- merge sort — A divide-and-conquer sort that splits the list in half, sorts each half recursively and then merges the two sorted halves.
- radix sort — A non-comparison sort that sorts integers one digit at a time, using a stable sort such as counting sort for each digit.
- sorted() — sorted(items) returns a new sorted list from any iterable; items.sort() sorts a list in place and returns None.
- key function — A function given as key= to sorted, sort, min or max, which turns each item into the value to compare by.
Taught in
- What A Hash Function Promises — Algorithms & Data Structures for Working Engineers
- Hash Tables: Chaining, Open Addressing And Load Factor — Algorithms & Data Structures for Working Engineers
- Collisions In Practice And Hash Flooding — Algorithms & Data Structures for Working Engineers
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers
- Counting And Radix Sort: Beating N Log N — Algorithms & Data Structures for Working Engineers
- Sorting In Real Systems: Stability, Keys And External Sort — Algorithms & Data Structures for Working Engineers
- Sorting, Keys And Lambdas — Hands-on Python: Complete Video Course & Book