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^{2}) 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.

- Click on above to restart the animations in a row, a column, or the entire table.
- Click directly on an animation image to start or restart it.
- Click on a problem size number to reset all animations.

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

*Algorithms in Java, Parts 1-4, 3rd edition*
by Robert Sedgewick.
Addison Wesley, 2003.

*Programming Pearls*
by Jon Bentley.
Addison Wesley, 1986.

*Quicksort is Optimal*
by Robert Sedgewick
and Jon Bentley,
Knuthfest, Stanford University, January, 2002.

Dual Pivot Quicksort: Code and Discussion.

*Bubble-sort with Hungarian ("Csángó") folk dance * YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

*Select-sort with Gypsy folk dance * YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

Sorting Out Sorting, Ronald M. Baecker with the assistance of David Sherman, 30 minute color sound film, Dynamic Graphics Project, University of Toronto, 1981. Excerpted and reprinted in SIGGRAPH Video Review 7, 1983. Distributed by Morgan Kaufmann, Publishers. Excerpt.