Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors

Comparison of Sorting Algorithms

Comparison of some commonly used sorting algorithms based on their key characteristics:

1. Time Complexity:

  • Bubble Sort: O(n2)
  • Selection Sort: O(n2)
  • Insertion Sort: O(n2)
  • Merge Sort: O(n log n)
  • Quick Sort: O(n log n) average case, O(n2) worst case
  • Heap Sort: O(n log n)
  • Radix Sort: O(d * (n + k)), where ‘d’ is the maximum number of digits, ‘n’ is the number of elements, and ‘k’ is the range of digits.

2. Space Complexity:

  • Bubble Sort: O(1)
  • Selection Sort: O(1)
  • Insertion Sort: O(1)
  • Merge Sort: O(n)
  • Quick Sort: O(log n) for the recursive call stack (in-place sorting can achieve O(1) auxiliary space)
  • Heap Sort: O(1)
  • Radix Sort: O(n + k), where ‘n’ is the number of elements and ‘k’ is the range of digits.

3. Stability:

  • Bubble Sort: Stable
  • Selection Sort: Not stable
  • Insertion Sort: Stable
  • Merge Sort: Stable
  • Quick Sort: Not stable
  • Heap Sort: Not stable
  • Radix Sort: Stable

4. Best Case Scenario:

  • Bubble Sort: O(n) when the list is already sorted
  • Selection Sort: O(n2)
  • Insertion Sort: O(n) when the list is already sorted
  • Merge Sort: O(n log n)
  • Quick Sort: O(n log n)
  • Heap Sort: O(n log n)
  • Radix Sort: O(d * (n + k)), where ‘d’ is the maximum number of digits, ‘n’ is the number of elements, and ‘k’ is the range of digits.

5. Worst Case Scenario:

  • Bubble Sort: O(n2)
  • Selection Sort: O(n2)
  • Insertion Sort: O(n2)
  • Merge Sort: O(n log n)
  • Quick Sort: O(n2)
  • Heap Sort: O(n log n)
  • Radix Sort: O(d * (n + k)), where ‘d’ is the maximum number of digits, ‘n’ is the number of elements, and ‘k’ is the range of digits.