What Are Adaptive Sorting Algorithms?

A non-adaptive algorithm does the same amount of work no matter what. Heap Sort and Selection Sort always perform their full O(n log n) or O(n²) routine even on an already-sorted array. An adaptive algorithm detects order and short-circuits: Insertion Sort runs in O(n) when the array is nearly sorted because each element only needs to move a short distance.

Insertion Sort and Bubble Sort (with an early-exit swapped flag) are adaptive. Tim Sort is the champion of adaptivity — it actively scans for pre-sorted 'runs' and merges them, which is exactly why it is the default sort in Python, Java, and JavaScript. Merge Sort, Heap Sort, and Selection Sort are non-adaptive.

In the visualizer, generate a nearly-sorted array and run Insertion Sort: it finishes almost instantly. Then run Selection Sort on the same array and watch it grind through the full O(n²) routine regardless. That contrast is adaptivity made visible.

"Nearly sorted" sounds imprecise, but it has formal definitions, and they are what algorithm designers actually optimise against. The common measures of presortedness are:

• Inversions — the number of pairs that are in the wrong relative order. A sorted array has zero; a reversed array has the maximum, n(n−1)/2. Insertion Sort runs in O(n + inversions), which is the cleanest statement of why it is fast on almost-sorted input.
• Runs — the number of already-ascending stretches the array breaks into. A sorted array is one run. This is the measure Tim Sort optimises for directly: it finds the runs and merges them rather than re-sorting from scratch.
• Removals — the fewest elements you would have to delete to leave a sorted sequence. Useful for describing data that is sorted apart from a handful of stragglers.

These measures matter because they explain why different adaptive algorithms behave differently on the same input. An array of 10,000 elements where two adjacent items are swapped has very few inversions and only three runs, so both Insertion Sort and Tim Sort handle it almost instantly. But an array built by interleaving two sorted halves has a huge number of inversions while consisting of just two runs — so Tim Sort finishes almost immediately by merging the two runs, while Insertion Sort has to shift enormous numbers of elements and crawls. Same "nearly sorted" intuition, opposite outcomes.

You can reproduce this in the visualiser: sort an array, note the comparison count, then run the same algorithm again on the sorted output. Insertion Sort's count collapses to n−1 while Selection Sort's does not move at all — that gap is adaptivity, measured directly.