AI Reasoning Steps with Collapsible Thinking

For nearly-sorted data, Insertion Sort and TimSort are your best options, depending on the data size:

Insertion Sort is ideal for small arrays (under ~1000 elements). It runs in O(n) time when data is nearly sorted because each element only needs to move a few positions. It's simple, in-place, and has minimal overhead.

TimSort is the better choice for larger datasets. It's specifically designed to exploit existing order in data by detecting natural "runs" of sorted elements and merging them efficiently. It powers Python's sorted() and Java's Arrays.sort() for good reason — its best-case is O(n) and it gracefully handles mixed data.

If your data has a specific structure where each element is at most k positions away from its final position, you can use a min-heap of size k to sort in O(n log k) time, which outperforms general-purpose algorithms when k is small.