### Implementation:

Implementation of 10 sorting algorithms can be found here, including

1. SelectionSort
2. InsertSort
3. ShellSort
4. BubbleSort
5. HeapSort
6. QuickSort
7. MergeSort
8. CountingSort
| 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.