partition! ordering functions

[jariji]

I'm wondering whether it would be useful to have a partition function in Base. This function is like sort!ing by a boolean predicate but can run quickly, because elements with the same value of the predicate do not need to be compared.

Reorders the elements of this iterator in-place according to the given predicate, such that all those that return true precede all those that return false. Returns the number of true elements found.

Rust https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.partition_in_place
C++ https://en.cppreference.com/w/cpp/algorithm/partition and https://en.cppreference.com/w/cpp/algorithm/stable_partition

[LilithHafner]

We have similar functions in sorting internals, it's likely just a matter of defining a public API for them. Do you have a use case for partition! which motivates this?

[jariji]

What brought it to mind was this presentation (timestamped video). He uses stable_partition to move selected UI elements into a contiguous group. I'm not sure how common a need it is, so perhaps it's better kept out of Base, or maybe once it's there we'll see it cropping up all over.

It also occurred to me that instead of making 2 groups it could take a function returning one of 1:k and make Val(k) groups and return a k-tuple of ranges, but maybe that's too much.

Probably best to wait until someone has more concrete use cases.