Sorting Algorithms

We all know that Quicksort is one of the fastest algorithms for sorting. It's not often, however, that we get a chance to see exactly how fast Quicksort really is. The following applets chart the progress of several common sorting algorithms while sorting an array of data using in-place algorithms. This means that the algorithms do not allocate additional storage to hold temporary results: they sort the data in place.

Some of these sorts are very stupid or very slow and should not be used in code. The use of Bubblesort is deprecated. So don't use Bubblesort! Also, don't use Swapsort! It is only a demonstration of the amount of time Java takes to swap n elements.

In-Place Mergesort is yet another abomination. Mergesort is supposed to run in O(n log n), but the implementation here runs in O(n * n). This is because a temporary scratch array is not used. As with most of the examples here, In-Place Mergesort sorts the elements in the array without using additional storage (other than the stack used for the recursive calls, and temporary variables). Jack Snoeyink has provided me with a the Double Storage mergesort algorithm sort implementation that uses a scratch array.

New: Radix sort by Alvin Raj, August 13, 2002.

Bubble Sort (by James Gosling and Jason Harrison)

Bi-Directional Bubble Sort (by James Gosling)

Selection Sort (by Jason Harrison)

Shaker Sort (by Jason Harrison)

Insertion Sort (by Jason Harrison)

In-Place Merge Sort (by Jason Harrison)

Double Storage Merge Sort (by Jack Snoeyink)

Comb Sort 11 (by Jason Harrison)

Shell Sort (by Jason Harrison)

Heap Sort (by Jason Harrison)

Quick Sort (by James Gosling)

Quick Sort with Bubblesort (by Jim Boritz)

Enhanced Quick Sort (by Jim Boritz)

Fast Quick Sort (by Denis Ahrens)

Radix Sort Algorithm (by Alvin Raj) LinkedQueue.java and intNode.java