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