True - that's a good point. One piece to keep in mind, though, is that this is only sorting lists of length `k`, where `k` is the number of neighbors (typically ~1-50), so it shouldn't be a huge penalty even in the rare worst-case.

Can you think of a good route that doesn't involve re-implementing a more sophisticated sort?