Sorting Algorithm Comparisons


Sorting Algorithm Comparisons Table

Criteria Bubble Selection Insertion Merge Quick Counting Timsort
Technique Brute force Brute force Brute force Divide-and-conquer Divide-and-conquer Non comparison Hybrid
Worst Time O(n2) O(n2) O(n2) O(nlgn) O(n2) O(k+n) O(nlgn)
Average Time Θ(n2) Θ(n2) Θ(n2) Θ(nlgn) Θ(nlgn) Θ(k+n) Θ(nlgn)
Best Time Ω(n) Ω(n2) Ω(n) Ω(nlgn) Ω(nlgn) Ω(k+n) Ω(n)
Space O(1) O(1) O(1) O(n) O(n) O(k+n) O(n)
Stable Yes No Yes Yes No Yes Yes
In-place Yes Yes Yes No Yes No
Online No No Yes No No No No
Adaptive Yes No Yes No Yes No Yes
Suitable for Sorted list Almost sorted list List with unknown order 0<=A[i]<=k

Criteria Explanation

  • Technique: Methodology of the sorting algorithm.
  • Worst Time: Worst time complexity (Big-O) of the algorithm.
  • Average Time: Average time complexity (Big-Theta) of the algorithm.
  • Best Time: Best time complexity (Big-Omega) of the algorithm.
  • Space: Space complexity of the algorithm.
  • Stable: Stable algorithm maintains the relative order of input elements with equal values.
  • In-place: In-place algorithm does not use auxiliary data structure to transform the input elements.
  • Online: Online algorithm does not require the entire input available from the start.
  • Adaptive: Adaptive algorithm takes the advantages of presorted array elements.

Reference