In place sorting is one of the most pedagogical exercises to introduce algorithmics. The goal of the sort vizualiser is to present students with a visual way to understand the way the most common algorithms work and how different approaches can yield different results in different conditions. This approach is directly inspired from work by Ron Baecker from the University of Toronto, that was presented in a famous paper and video: "Sorting out sorting", Siggraph 80.
I hope this java applet should help students understand the intricacies of sorting, but also popularize a vizualisation method as a pedagogical tool to teach algorithmics. I propose first an introduction to the main known algorthms, with complete source code in Java. Then the visualizer allows the actual comparisons of sorts in an intuitive way. Of course, one must understand that performance on a small array (100) may or may not scale to various larger sizes. However, we feel that the visualization of the chosen strategy is the important point of this visualizer.
Main approaches on sorting
Sorting an array of a list of item is one of the base and most usefull data process. Here, we assume we have to sort an array (meaning we can access in constant time any item of the collection). Some of the algorithms we present can be used with other data-structures like linked lists, but we don't focus on this.
The most classical approach is called in-place, comparison based sorting. The sort visualizer presents only examples in this category. In place sorting means that, to save memory, one does not allow use of additional storage besides the items being compared or moved. Comparison-based sort means that we have a function (compare(a,b)) that can only tell if a<b, a>b or a=b. No other information on the keys is available, such as the ordinality of the items, nor is it possible to logically group them by any mean prior to sorting. Under such restrictions, any algorithm will require at least log n! (or O(n log n)) comparisons of one item again another to sort some array in the worst case. Any type of sort requires at least n moves in the worst case.
Non-comparison based sorts (radix sort, bucket sort, hash-tables-based, statistically based approaches...) assume that one can extract some ordinal information in the keys, and use it to improve the efficiency of the algorithm. For instance, to sort 100 integers, it is easier to group them by order of magnitude in one phase (0-9, 10-19...90-99...), then to sort the groups internally. Having more information on the key's range and structure allows to sort faster, often in linear time.
Sorts with additional buffers (merge sorts, quicksort (indirectly)...): Having a buffer to store intermediate results such as already sorted subportions of the array can help the efficiency of the algorithm, by reducing the number of moves that have to be performed. Nevertheless, it is not possible to go below the barrier of log n! comparisons in the worst case for comparison based sorts.
Other links on sorting
There are numerous on line courses and Java demos of sorting algorithms, most of the interactive demos are taken from a visualization developped at Sun, which I find personnaly less 'talking' than the sort visualizer.
Here are some links I find truly usefull (in 1998!) to look at: