Animated Sorting Algorithm Demo: 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, but such an algorithm has not yet been discovered. Shell sort is the only sub-quadratic algorithm that is also adaptive in this case.

Directions

• Click on to restart the animations.
• Click on a size number to change the size of the examples.
• Click on a cell to restart an individual animation.
• Click on a cell title to explore that algorithm.

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