Implementation:
Implementation of 10 sorting algorithms can be found here, including
- SelectionSort
- InsertSort
- ShellSort
- BubbleSort
- HeapSort
- QuickSort
- MergeSort
- CountingSort
- RadixSort
- BucketSort
Animation for above soring algorithms can be found here.
Comparison:
| Algorithm | Average Time | Worst Time | Best Time | Stable? | Auxiliary Space | Constraints |
|---|---|---|---|---|---|---|
| SelectionSort | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $\checkmark$ | $C$ | |
| InsertSort | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $\checkmark$ | $C$ | |
| ShellSort | N/A | N/A | N/A | x | $C$ | |
| BubbleSort | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $\checkmark$ | $C$ | |
| HeapSort | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | x | $C$ | |
| QuickSort | $O(nlogn)$ | $O(n^2)$ | $O(nlogn)$ | x | $C$ | |
| MergeSort | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $\checkmark$ | $n$ | |
| CountingSort | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | $\checkmark$ | $n+k+C$ | non-negative and within some range |
| RadixSort | $O(n)$ | $O(n)$ | $O(n)$ | $\checkmark$ | $n+k+C$ | non-negative |
| BucketSort | $O(n)$ | $O(n)$ | $O(n)$ | $\checkmark$ | $2n+C$ | elements distribute in buckets evenly and independent |
Note: $C$ is a small constant; $k$ is the max element; $n$ is the number of total elements. N/A means it depends on selection of increment value.