Nearly Sorted Initial Order

Sorting nearly sorted data is quite common in practice. Some observations:

• Insertion sort is the clear winner on this initial condition.
• Bubble sort is fast, but insertion sort has lower overhead.
• Shell sort is fast because it is based on insertion sort.
• Merge sort, heap sort, and quick sort do not adapt to nearly sorted data.

Insertion sort provides a O(n²) worst case algorithm that adapts to O(n) time when the data is nearly sorted. One would like an O(n·lg(n)) algorithm that adapts to this situation; smoothsort is such an algorithm, but is complex. Shell sort is the only sub-quadratic algorithm shown here that is also adaptive in this case.

• Black values are sorted.
• Gray values are unsorted.
• A red triangle marks the algorithm position.
• Dark gray values denote the current interval (shell, merge, quick).
• A pair of red triangles marks the left and right pointers (quick).