Stable sorting
Not met yet
A sort is stable if items that tie keep the order they started in. Python's sorted() and .sort() are stable, so sorting parts by weight keeps parts of the same weight in the order they arrived. That means you can sort by two things in two passes: sort by the one that matters less, then by the one that matters more. Merge sort is stable if it takes from the left pile on a tie; selection sort's long swaps make it unstable. Python's own sort is stable and O(n log n), a mix of merge sort and insertion sort, written in C.
Try it
main.pyOutput
Press Run and what your program prints shows up here.
Easy to get wrong
- Thinks sorting with a key breaks ties using the rest of the item, such as the name.
- Thinks items that tie come out of a sort in an unpredictable order.
- Thinks sorting a second time throws away the order the first sort made, even among items that tie.
- Thinks selection sort keeps items that tie in the order they started in.