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
  9. RadixSort
  10. 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.