Nearly Sorted Insertion Sort
Sort an almost ordered sequence efficiently by using insertion sort, whose running time improves when few elements are far from their final positions.
Tag
Nearly-Sorted
2 notes
2 notes
Sort an almost ordered sequence efficiently by using insertion sort, whose running time improves when few elements are far from their final positions.
Exploit near-sorted structure in inputs like append-only logs or incremental updates to sort in linear or near-linear time.