Feature request: incremental sort

[Lucretiel]

An incremental sort would make an excellent addition to itertools's lazy iterator model.

The basic idea of an incremental sort is that you can sort the sequence one element at a time, where the cost of extracting each individual element is only (approximately) O(log(k)), where k is the number of elements that have already been extracted. For instance:

let data: Vec<i64> = build_data().collect();  // Very long list. Let's say a million elements
let result = data.iter().sorted_incremental().filter(pred).take(100);

Let's say the predicate pred returns half of all elements it's given. This means that the sorted_incremental only has to emit the first 200 elements or so when the final result is evaluated, rather than having to sort the whole list. Better still, a good algorithm can do this partial sort in O(N + k log(k)), where N is the total size of the list and k is the number of extracted, sorted elements

A more formal definition of the problem can be seen here and one person's sample C++ implementation here

(Adapted almost verbatim from https://github.com/immutable-js/immutable-js/issues/908)

[scottmcm]

Related: https://github.com/rust-lang/rust/pull/76234

[Philippe-Cholet]

I like the idea of this sorted_incremental. It heavily makes me think of the recent #925.

@scottmcm Do you have some recent insight on this?