« Back to all algorithms and all initial conditions

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(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).