VecDeque has no `sort_by` method (should possibly have one to match Vec).

[mitchmindtree]

I just came across a use case for this while working on a visit order for the UI graph in conrod - its absence took me by surprise 😸

Is there a particular reason this hasn't been implemented yet? Or has it just not popped up yet (pun intended)?

[tamird]

How come either method has to be inherent? Seems like this could be a trait that requires sort and provides sort_by.

[abonander]

sort and sort_by are methods provided by [T]. Since the sorting algorithm requires 2 * n extra space, I don't see a too much problem with copying the data from the disjoint slices into one allocation to sort and then putting it back in-order. It's mostly just a question of semantics.

[retep998]

Wouldn't it have to be sort_by which is required and sort have a default implementation?
I'd prefer if VecDeque had an optimal in place sorting algorithm though.

[Gankra]

@retep998 the thing is std has no optimal or inplace sorting! All we have is naive merge sort (because it was argued that our sort should be stable). Our sort support is a bit trash imo. Quicksort (unstable) or wikisort (stable but complicated) would be good to have here. Maybe even expose insertionsort!

Even then, it's genuinely unclear to me what would be optimal here. Seems like linearizing the array to make it contiguous and avoid modulo logic could yield huge benefits.

[petrochenkov]

sort is stable? o_O
At least a good thing is that it's not documented, it's still possible to fix it and add stable_sort as a separate function.

[Gankra]

Changing that may be an unacceptable break.

[abonander]

It'd be cool, if a little overkill, to have a crate with a bunch of different sorting functions. That might make a good crate for contain-rs.

[bluss]

Oh no, we haven't documented that it's a stable sort. That's a strange oversight.

[petrochenkov]

@bluss

Oh no, we haven't documented that it's a stable sort.

"Oh yes" you mean?
Why should sort be stable by default? Stability is not usually needed. "Don't pay for what you don't use" and everything like this.

[Gankra]

The current situation was definitely an active decision. I'm having trouble finding it, though.

I basically agree that it's a weird cost, but there's possibly an argument to be had that it's the "safer" default, and unstable_sort could easily be the opt-in to less reliable behavior.

[bluss]

@petrochenkov It should be stable by default because a stable sort is more versatile. Reordering equally ordered elements in sort is a potential gotcha, too, and Rust wants to be a nice language. The third party crate space is open to find other sorting algorithms with different tradeoffs.

[Gankra]

Some discussion:

#11064