Some way to perform in-place sorting in iterator chains?

[leonardo-m]

In the Python language sort() doesn't return the sorted items, probably to better remind the programmer that sort is a procedure that works in-place (there is a sorted() function, that returns the sorted items, but it copies the input, so it's not in-place):

>>> a = [10, 5, 1, 6]
>>> a.sort()
>>> a
[1, 5, 6, 10]
>>> sorted([10, 5, 1, 6])
[1, 5, 6, 10]

In D language the chains of ranges (similar to the Rust chains of iterators) are quite common, so the D standard library uses an intermediate solution:

void main() {
    import std.stdio, std.algorithm;
    writeln([10, 5, 1, 6].sort().release());
}

In D sort() doesn't return the sorted items, but a SortedRange struct that denotes that the items it refers to are sorted (and this struct allows nice binary searches and other quite useful things, that are not possible equally nicely in Rust) and you can pull out the sorted items using the SortedRange.release() method. This allows to both use sort() in range chains and avoid bugs.

Currently in Rust you can't use sort() in iterator chains():

fn main() {
    let mut arr = [10, 5, 1, 6];
    arr.sort();
    println!("{:?}", arr);
}

Can we improve this situation in some way?

• Changing the return type of sort() is probably a breaking change now.
• Adding iterator methods like sorted() and sorted_by_key() (that internally create a vector of items, sort it and return it) could help, but it doesn't solve the general problem.
• So a solution is to add some new sort methods (and deprecate the old ones in Rust 2.0).

[Thiez]

What would be the advantages of this addition, aside from bringing Rust more in line with Python and D? You can already sort in various ways: Iterator::collect into something that is already sorted , e.g. BinaryHeap, BTreeMap, BTreeSet, or you can collect into a Vec and call one of slice::sort slice::sort_by, slice::sort_by_key.

[leonardo-m]

What would be the advantages of this addition, aside from bringing Rust more in line with Python and D?

Python doesn't have chains of lazy iterables like D, Rust, F# and other languages, so this change is unrelated to Python.

The purposes of this change are:

• To allow sorting in iterator chains (without breaking them in parts, with assignments to intermediate variables), while keeping the programmer aware that this specific kind of sorting is still in-place (unless the sorted() of Python).
• If this idea is implemented similarly to D language, it opens the door to some quite interesting/smart usages of sorted iterables. (Example: a grouping of a sorted iterator is still a sorted iterator, a filtering of a sorted iterator is still a sorted iterator, and so on). I am not sure we can do the same as in D, because in D a SortedRange brings within its type the comparison function the data is sorted according to.

some_iterator
.collect::<Vec<_>>()
.inplace_sort()
.contents()

Some use cases are covered by adding an iterator method like sorted() that calls collect::<Vec<_>> inside itself. While this doesn't cover all cases, it's backward compatible, and it's simpler to use correctly.

[Thiez]

Sorting of slices in the Rust standard library is not actually in place. :-)

The usual process for adding things to the standard library is to write and submit an rfc. The steps are explained here. Something similar to what you propose is already available in the itertools crate, so part of evaluating whether this should be in the standard library could be researching how many crates have itertools as a dependency and use that method. Personally I think maybe a trait extending Iterator that indicates that the data is sorted would be really cool, but I suspect I actually wouldn't ever need it in practice.

[leonardo-m]

Sorting of slices in the Rust standard library is not actually in place. :-)

Right, "in place sorting" has a technical meaning. What I was trying to say is "modifies the input data, instead of copying it and sorting the copy".

Yes, there are some things in the itertools crate that in my opinion should be moved in the std library.

The sorted/sorted_by of itertools are indeed the partial solutions I was thinking about. But the "full solution" is more like the sort() of D language, that modifies the input data and returns some view of it, instead of copying it and sorting the copy as sorted().

Personally I think maybe a trait extending Iterator that indicates that the data is sorted would be really cool, but I suspect I actually wouldn't ever need it in practice.

I think listing some usage examples could help show why people would find it useful in practice. But this is for the RFC...

[dtolnay]

I agree that this could be handled better by the standard library. The approach in D is really neat! I think the best path forward would be an RFC to suggest a concrete API for this in Rust.