9. Partial, Online, and Adaptive Sorting
Sorting under constraints: partial sort, online insertion, adaptive merge, Timsort internals, and lazy or order-maintenance sorting.
7 notes
Sorting under constraints: partial sort, online insertion, adaptive merge, Timsort internals, and lazy or order-maintenance sorting.
Maintain a dynamically ordered sequence under insertions and comparisons without fully re-sorting.
Maintain sorted order over a moving window of the most recent elements in a stream.
Maintain a sorted sequence by inserting elements into a binary search tree as they arrive and extracting them in order.
Maintain a valid topological ordering of a directed acyclic graph as vertices or edges are added over time.
Sort a sequence as elements arrive by inserting each new item into its correct position among the items already seen.
Maintain a sorted sequence while elements are inserted one by one, updating order incrementally.