jcjohnson/sorting.js

sorting.js

A visualization for a bunch of different sorting algorithms in Javascript.

See a demo here: http://cs.stanford.edu/people/jcjohns/sorting.js/

More specifically, we visualize in-place comparison-based sorting algorithms by highlighting each comparison in blue and each swap in red. Currently the following sorting algorithms are implemented:

• Bubble sort
• Selection sort
• Insertion sort
• Odd-even sort
• Cocktail sort
• Quicksort
• Heapsort
• Merge sort
• Bitonic mergesort
• Introsort

Quicksort and introsort recursively partition chunks of the array around a pivot value; the choice of pivot can have a big effect on the efficiency of the algorithm. We implement several pivoting choices discussed here.

The current mergesort implementation isn't really in-place; during the merge step, we scan the sorted subarrays to build up a permutation that will merge them, then convert the permutation to a sequence of swaps. These intermediate data structures use a linear amount of extra memory.

For the bitonic mergesort I followed this implementation. Because I am lazy, the bitonic mergesort implementation only supports arrays whose lengths are a power of two, and array lengths will be rounded up to the nearest power of two if bitonic mergesort is selected.