Toptal connects the top 3% of freelance developers all over the world.
Nearly Sorted Initial Order
Animation, code, analysis, and discussion of 8 sorting algorithms on nearly sorted initial order.
How to use: Press "Play all", or choose the 
button.
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(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.
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).
