Sorting nearly sorted data is quite common in practice. Some
- 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(n2) 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).