# 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
Bozo sort O(n*n!) O(n*n!) Unstable Random Average time is asymptotically half that of bogosort.
Source: BozoSortAlgorithm.java
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
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
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
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
Bidirectional Bubble sort O(n) O(n2) Stable Exchanging Aka. Cocktail sort.
Source: BidirectionalBubbleSortAlgorithm.java
Comb sort 11 O(nlog n) O(nlog n) O(nlog n) Unstable Exchanging
Source: CombSort11Algorithm.java
Gnome sort O(n) O(n2) Stable Exchanging
Source: GnomeSortAlgorithm.java
Selection sort O(n2) O(n2) O(n2) Unstable Selection
Source: SelectionSortAlgorithm.java
Bidirectional Selection sort O(n2) O(n2) O(n2) Unstable Selection Aka. Shaker sort.
Source: BidirectionalSelectionSortAlgorithm.java
Insertion sort O(n) O(n + d) O(n2) Stable Insertion d is the number of inversions, which is O(n2).
Source: InsertionSortAlgorithm.java
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
Shell sort O(n1.5) Unstable Insertion
Source: ShellSortAlgorithm.java
Merge sort O(nlog n) O(nlog n) O(nlog n) Stable Merging Uses O(n) memory.
Source: ExtraStorageMergeSortAlgorithm.java
In-place merge sort O(nlog n) O(nlog n) O(nlog n) Stable Merging Uses O(1) memory.
Source: MergeSortAlgorithm.java
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
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
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
Patience sort O(n) O(nlog n) Unstable Insertion Finds all the longest increasing subsequences within O(n log log n).
Source: PatienceSortAlgorithm.java
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
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.
Bucket sort O(n) O(n) O(n2) Stable Buckets Bucket sort is a generalization of pigeonhole sort.
Source: BucketSortAlgorithm.java
Binary bucket sort O(n) O(n) O(n2) Buckets
Source: BinaryBucketSortAlgorithm.java
Quick binary bucket sort O(n) O(n) O(n2) Buckets
Source: QuickBinaryBucketSortAlgorithm.java
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
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