Best Sorting Algorithm for Nearly Sorted Data
Nearly-sorted data is extremely common — append a few records to an ordered log, or fix a handful of out-of-place entries. For these inputs, adaptive sorting algorithms can finish in near-linear time, dramatically faster than their worst case.
Insertion Sort is the simple winner
Insertion Sort reaches O(n) when only a few elements are out of place, because each element shifts only a short distance. For small or nearly-sorted arrays, nothing simpler beats it.
Tim Sort is the production winner
Tim Sort was designed for exactly this. It detects pre-sorted runs and merges them, reaching O(n) on already-sorted data and O(n log n) worst case — all while staying stable. This adaptivity is why it is the default in Python, Java, and JavaScript.
What to avoid
Non-adaptive sorts waste the existing order. Selection Sort and Heap Sort do their full routine regardless, and naive Quick Sort can even hit O(n²) on sorted data. Read more in adaptive sorting algorithms.
Frequently asked questions
Which sorting algorithm is best for nearly sorted data? +
Why is Insertion Sort good for almost-sorted data? +
See it in motion
Watch this algorithm and 9 others run step by step in our free interactive visualizer.
▶ Launch Visualiser