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.