Description
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 immutable-js/immutable-js#908)