But how the data got sorted is irrelevant to the speed of the algorithm: for example, you could use binary search as part of an algorithm to find the insertion point of a new element in an always sorted data structure, meaning that sorting the data is never necessary.
The overall journey matters. For example, for some flight journeys, the flight-time is only a fraction of the overall time taken by the journey, which could makes it faster if you use road or rail transport. Flight speed doesn't matter.
But that is an unanswerable question which depends on how the data structure is used. The reasonable thing is to calculate the cost for the operations separately and let whoever uses the algorithms figure out what that means for their use case.