# Sorting algorithms: implementation and comparison

### 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.