| 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 [email protected]. | ||||||||
| 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:
|
||||||||
|
See Also: Duelling Algorithms |
||||||||
