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(n^{2.71})  O(n^{2.71})  O(n^{2.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(n^{2})  Unstable  Exchaning  
Source: SiftSortAlgorithm.java  

Bubble sort  O(n)  —  O(n^{2})  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(n^{2})  —  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(n^{2})  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(n^{2})  Stable  Exchanging  
Source: GnomeSortAlgorithm.java  
See also: Insertion sort  

Selection sort  O(n^{2})  O(n^{2})  O(n^{2})  Unstable  Selection  
Source: SelectionSortAlgorithm.java  
See also: Bidirectional selection sort, Heap sort  

Bidirectional Selection sort  O(n^{2})  O(n^{2})  O(n^{2})  Unstable  Selection  Aka. Shaker sort.  
Source: BidirectionalSelectionSortAlgorithm.java  
See also: Selection sort, Heap sort  

Insertion sort  O(n)  O(n + d)  O(n^{2})  Stable  Insertion  d is the number of inversions, which is O(n^{2}).  
Source: InsertionSortAlgorithm.java  
See also: Flash sort, Shell sort  

Flash sort  O(n)  O(n + d)  O(n^{2})  —  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(n^{1.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: Inplace merge sort, Bitonic sort  

Inplace 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, Inplace 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 inplace 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(n^{2})  Unstable  Partitioning  
Source: QSortAlgorithm.java  
See also: 3way quick sort, Qubble sort, Enhance quick sort, Fast quick sort  

3way quick sort  O(nlog n)  O(nlog n)  O(n^{2})  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(n^{2})  Unstable  Partitioning/Exchanging  Bubble sort if the number of elements in a partition is less than 6.  
Source: QubbleSortAlgorithm.java  
See also: 3way quick sort, Quick sort, Enhance quick sort, Fast quick sort  

Enhanced quick sort  O(nlog n)  O(nlog n)  O(n^{2})  Unstable  Partitioning  
Source: EQSortAlgorithm.java  
See also: 3way quick sort, Quick sort, Qubble sort, Fast quick sort  

Quick sort w/ Insertion sort  O(nlog n)  O(nlog n)  O(n^{2})  Unstable  Partitioning/Insertion  Insertion sort if the number of elements in a partition is less than 4.  
Source: FastQSortAlgorithm.java  
See also: 3way 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: 3way 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(n^{2})  Stable  Buckets  Bucket sort is a generalization of pigeonhole sort.  
Source: BucketSortAlgorithm.java  
See also:  

Binary bucket sort  O(n)  O(n)  O(n^{2})  —  Buckets  
Source: BinaryBucketSortAlgorithm.java  
See also:  

Quick binary bucket sort  O(n)  O(n)  O(n^{2})  —  Buckets  
Source: QuickBinaryBucketSortAlgorithm.java  
See also:  

Counting sort  O(n + 2^{k})  O(n + 2^{k})  O(n + 2^{k})  —  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:  

Oddeven transposition sort  —  —  O(n)  —  Merging  Batcher's oddeven (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(n^{1/2}log n)  —  Merging  Absolute Efficiency: O(1/(n^{1/2})), when running on n processors.  
Source: ShearSortAlgorithm.java  
See also:  
Download:


See Also: Duelling Algorithms 