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.