Nearly Sorted Initial Order

Discussion

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.

Directions

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

Key

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

References

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.