Sorting Algorithms Demonstration in Java

I wrote little of this code, and take no responsibility (nor credit) for any of it.

Demo Applet Algorithm Name Running Time (Efficiency) Stability Method Other notes
Best Average Worst
If you have any other sorting algorithms you would like to see included on this list please send them to mailinglistsandjunkmailandcrap@wcgwave.ca.
Bogosort O(n*n!) O(unbounded) Unstable Random Average time using Knuth shuffle.
Source: BogoSortAlgorithm.java
See also: Bozo sort, Perm sort, Stooge sort
Bozo sort O(n*n!) O(n*n!) Unstable Random Average time is asymptotically half that of bogosort.
Source: BozoSortAlgorithm.java
See also: Bogo sort, Bozo sort, Stooge sort
Perm sort O(n) O(n*n!) Unstable Exchanging The algorithm works by trying every permutation until it finds one that's sorted.
Source: PermSortAlgorithm.java
See also: Bogo sort, Bozo sort, Stooge sort
Stooge sort O(n2.71) O(n2.71) O(n2.71) Unstable Exchanging The algorithm gets its name from slapstick routines of the Three Stooges, in which each stooge hits the other two.
Source: StoogeSortAlgorithm.java
See also: Bogo sort, Bozo sort, Perm sort
Sift sort O(n2) Unstable Exchaning
Source: SiftSortAlgorithm.java
Bubble sort O(n) O(n2) Stable Exchanging Times are for best variant.
Source: BubbleSortAlgorithm.java
See also: Bidirectional bubble sort, Bitonic sort, Qubble sort
Several unique sort O(n) O(n2) Exchanging This new sort makes as many passes as there are unique records in the field.
Several Unique runs in time less than T(kn), proportional to the number of unique elements and the total number of elements — which is equivalent to T(n2) in the worst case.
This algorithm was invented by a computer program, Criticall.
Several unique sort vs. Bubble sort duel on list with several unique items.
Source: SeveralUniqueSortAlgorithm.java
See also:
Bidirectional Bubble sort O(n) O(n2) Stable Exchanging Aka. Cocktail sort.
Source: BidirectionalBubbleSortAlgorithm.java
See also: Bubble sort, Bitonic sort, Qubble sort
Comb sort 11 O(nlog n) O(nlog n) O(nlog n) Unstable Exchanging
Source: CombSort11Algorithm.java
See also:
Gnome sort O(n) O(n2) Stable Exchanging
Source: GnomeSortAlgorithm.java
See also: Insertion sort
Selection sort O(n2) O(n2) O(n2) Unstable Selection
Source: SelectionSortAlgorithm.java
See also: Bidirectional selection sort, Heap sort
Bidirectional Selection sort O(n2) O(n2) O(n2) Unstable Selection Aka. Shaker sort.
Source: BidirectionalSelectionSortAlgorithm.java
See also: Selection sort, Heap sort
Insertion sort O(n) O(n + d) O(n2) Stable Insertion d is the number of inversions, which is O(n2).
Source: InsertionSortAlgorithm.java
See also: Flash sort, Shell sort
Flash sort O(n) O(n + d) O(n2) Insertion/? The flash sort algorithm consists of an initial "partial flash short" stage followed by a traditional insertion sort. The partial flash sort seems to decrease average insertion sort time noticably.
Source: FlashSortAlgorithm.java
See also: Insertion sort, Shell sort
Shell sort O(n1.5) Unstable Insertion
Source: ShellSortAlgorithm.java
See also: Insertion sort, Flash sort
Merge sort O(nlog n) O(nlog n) O(nlog n) Stable Merging Uses O(n) memory.
Source: ExtraStorageMergeSortAlgorithm.java
See also: In-place merge sort, Bitonic sort
In-place merge sort O(nlog n) O(nlog n) O(nlog n) Stable Merging Uses O(1) memory.
Source: MergeSortAlgorithm.java
See also: Extra storage merge sort, Bitonic sort
Bitonic Sorter O(n(log n)2)) Unstable Merging Requires list with a size that is a power of 2.
Designed for parallel processors.
Source: BitonicSortAlgorithm.java
See also: Extra storage merge sort, In-place merge sort, Bubble sort, Bidirectional bubble sort
Heap sort O(nlog n) O(nlog n) O(nlog n) Unstable Selection
Source: HeapSortAlgorithm.java
See also: Selection sort, JSort
JSort Unstable Selection/Insertion JSort is an in-place sort algorithm that uses build heap twice to largely order the array then finishes with an insertion sort. JSort is attributed to Jason Morrison.
Source: JSortAlgorithm.java
See also: Heap sort, Insertion sort
Quick sort O(nlog n) O(nlog n) O(n2) Unstable Partitioning
Source: QSortAlgorithm.java
See also: 3-way quick sort, Qubble sort, Enhance quick sort, Fast quick sort
3-way quick sort O(nlog n) O(nlog n) O(n2) Unstable Partitioning
Source: QSortXAlgorithm.java
See also: Quick sort, Qubble sort, Enhance quick sort, Fast quick sort
Quick sort w/ Bubble sort O(nlog n) O(nlog n) O(n2) Unstable Partitioning/Exchanging Bubble sort if the number of elements in a partition is less than 6.
Source: QubbleSortAlgorithm.java
See also: 3-way quick sort, Quick sort, Enhance quick sort, Fast quick sort
Enhanced quick sort O(nlog n) O(nlog n) O(n2) Unstable Partitioning
Source: EQSortAlgorithm.java
See also: 3-way quick sort, Quick sort, Qubble sort, Fast quick sort
Quick sort w/ Insertion sort O(nlog n) O(nlog n) O(n2) Unstable Partitioning/Insertion Insertion sort if the number of elements in a partition is less than 4.
Source: FastQSortAlgorithm.java
See also: 3-way quick sort, Quick sort, Qubble sort, Enhance quick sort
Introsort O(nlog n) O(nlog n) O(nlog n) Unstable Hybrid Introsort, or introspective sort, begins with quicksort, switching to heapsort once the recursion depth exceeds a preset value.
Sublists smaller than a certain threshold are sorted with insertion sort.
Source: IntroSortAlgorithm.java
See also: 3-way quick sort, Quick sort, Heap sort, Insertion sort
Patience sort O(n) O(nlog n) Unstable Insertion Finds all the longest increasing subsequences within O(n log log n).
Source: PatienceSortAlgorithm.java
See also:
Swap sort Swapping This isn't really a swap. This algorithm just demonstrates how long it takes java to perform n swaps.
Source: SwapSortAlgorithm.java
See also:
Radix sort O(n(k/b)) O(n(k/b)) O(n(k/b)) Stable Buckets/Counting Least significant variety of radix sort.
k is the maximum key value.
b is the base in which the key is evaluated.
Source: RadixSortAlgorithm.java, LinkedQueue.java, intNode.java
See also:
Bucket sort O(n) O(n) O(n2) Stable Buckets Bucket sort is a generalization of pigeonhole sort.
Source: BucketSortAlgorithm.java
See also:
Binary bucket sort O(n) O(n) O(n2) Buckets
Source: BinaryBucketSortAlgorithm.java
See also:
Quick binary bucket sort O(n) O(n) O(n2) Buckets
Source: QuickBinaryBucketSortAlgorithm.java
See also:
Counting sort O(n + 2k) O(n + 2k) O(n + 2k) Buckets n and k are the lengths of the arrays A (the input array) and C (the counting array), respectively.
Source: CountingSortAlgorithm.java
See also:
Odd-even transposition sort O(n) Merging Batcher's odd-even (transposition) mergesort is a generic construction for sorting networks of size 2n.
Absolute Efficiency: O((log n)/n), when running on n processors.
Source: OETransSortAlgorithm.java
See also: Merge sort
Shear sort O(n1/2log n) Merging Absolute Efficiency: O(1/(n1/2)), when running on n processors.
Source: ShearSortAlgorithm.java
See also:

Download:

  • SortItem.java - the applet appearing above that animates the sorting algorithms.
  • SortAlgoritm.java - the abstract class that all sorting algorithms about extend.

See Also: Duelling Algorithms