描述
ImmutableJS doesn't seem to offer an incremental sort algorithm; this would make an excellent addition to its lazy data structures.
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:
const myList = List(...) // Very long list. Let's say a million elements
const result = myList.incrSort(cmp).filter(pred).take(100)
Let's say the predicate returns half of all elements it's given. This means that the incrSort 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