Animated Sorting Algorithm Demo: Merge Sort

Algorithm

m = n / 2
sort a[1..m] recursively
sort a[m+1..n] recursively
copy a[m+1..n] to temp space
merge
        

Properties

• Stable
• O(n) extra space (see below)
• Ω(n·lg(n)) time
• Completely non-adaptive

Discussion

If using O(n) extra space is of no concern, then merge sort is an excellent choice. It is simple to implement, and it is the only stable O(n·lg(n)) sorting algorithm.

There do exist linear time in-place merge algorithms (for the last step of the algorithm), but they are extremely complex. The complexity is justified for applications such as external sorting where the extra space is not available, but one of the important properties (stability) may be lost.

When sorting linked lists, merge sort requires only O(1) extra space. Given its many other advantages, merge sort is an excellent choice for sorting linked lists.

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 input order.

Key

• Black values are sorted.
• Gray values are unsorted.
• Dark gray values show the current sub-array that is being sorted recursively.
• A red triangle marks the algorithm position.

References

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