A $\text{stable sort}$ preserves the order of values that are equal with respect to the comparison function. We have a list of three-dimensional points
$[(7, 1, 8),(3, 5, 7),(6, 1, 4),(6, 5, 9),(0, 2, 5),(9, 0, 9)].$
We sort these in ascending order by the second coordinate. Which of the following corresponds to a stable sort of this input?
- $[(9, 0, 9),(7, 1, 8),(6, 1, 4),(0, 2, 5),(6, 5, 9),(3, 5, 7)]$
- $[(0, 2, 5),(3, 5, 7),(6, 1, 4),(6, 5, 9),(7, 1, 8),(9, 0, 9)]$
- $[(9, 0, 9),(7, 1, 8),(6, 1, 4),(0, 2, 5),(3, 5, 7),(6, 5, 9)]$
- $[(9, 0, 9),(6, 1, 4),(7, 1, 8),(0, 2, 5),(3, 5, 7),(6, 5, 9)]$
