Reversed Initial Order

Discussion

Sorting an array that is initially in reverse sorted order is an interesting case because it is common in practice and it brings out worse-case behavior for insertion sort, bubble sort, and shell sort.

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.