tag

#nearly-sorted

2 pages tagged

Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.16 Nearly Sorted Data

6.16 Nearly Sorted Data Nearly sorted inputs appear frequently in practice. Logs appended over time, incremental updates, and cached results often differ only slightly from sorted order. Algorithms that exploit this structure can run in linear or near-linear time. Problem You have an array A[0..n-1] that is close to sorted. You want to sort it faster than general-purpose O(n log n) algorithms. Measuring “Nearly Sorted” Several measures capture how far...

Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Nearly Sorted Insertion Sort

Nearly Sorted Insertion Sort Nearly sorted insertion sort is ordinary insertion sort applied to input that is already close to sorted order. Insertion sort adapts well to this case because each element moves only a short distance. You use it when the input has small disorder, such as data produced by appending a few new records, merging mostly ordered logs, or correcting a sequence after minor edits. Problem Given an...