Mergesort

These demos are intended to supplement (not replace!) Chapter 8 of Sedgewick's Algorithms book. You can find detailed descriptions, code, and other information about the algorithms in the book.

Each demo is a dynamic representation of the algorithm in action, sorting an array a containing a permutation of the integers 1 through N. For each i, the array element a[i] is depicted as a black dot plotted at position (i, a[i]). Thus, the end result of each sort is a diagonal of black dots going from (1, 1) at the bottom left to (N, N) at the top right. Each time an element is moved, a green dot is left at its old position. Thus the moving black dots give a dynamic representation of the progress of the sort and the green dots give a history of the data-movement cost.

The auxilliary array used in the merging operation is shown to the right of the array a[], going from (N+1, 1) to (2N, 2N).

Mergesort illustrates the operation of the basic algorithm.

Nonrecursive mergesort is a bottom-up version of mergesort.