[kazinator]

Yes, bingo.

And this is easy to then contrast with, say, sorting, to counter the earlier objection.

We can split the set into two, sort the two parts individually and then trivially merge the results. We cannot split the cities into two, solve the traveling salesman problem, and then easily merge the results.

And adding a new element to a sorted list is just a linear insertion.