Sort#

1. Comparison-Based Sorting#

These algorithms compare elements to determine their order.

a. Bubble Sort#

  • Repeatedly swaps adjacent elements if they are in the wrong order.
  • Time Complexity: O(n²)
  • Space Complexity: O(1)

b. Selection Sort#

  • Finds the smallest element and places it in the correct position.
  • Time Complexity: O(n²)
  • Space Complexity: O(1)

c. Insertion Sort#

  • Picks one element at a time and places it in its correct position.
  • Time Complexity: O(n²)
  • Space Complexity: O(1)
  • Efficient for small or nearly sorted data.

d. Merge Sort (Divide and Conquer)#

  • Divides the array into halves, sorts them, and merges them.
  • Time Complexity: O(n log n)
  • Space Complexity: O(n)

e. Quick Sort (Divide and Conquer)#

  • Picks a pivot, partitions the array, and sorts recursively.
  • Time Complexity: O(n log n) (Best & Avg), O(n²) (Worst)
  • Space Complexity: O(log n) (due to recursion)

f. Heap Sort#

  • Converts the array into a heap and extracts elements in order.
  • Time Complexity: O(n log n)
  • Space Complexity: O(1)

g. Shell Sort#

  • Variation of insertion sort that sorts elements at a gap.
  • Time Complexity: O(n log n) (Best), O(n²) (Worst)
  • Space Complexity: O(1)

2. Non-Comparison-Based Sorting#

These algorithms do not compare elements directly.

a. Counting Sort#

  • Counts occurrences of elements and places them in sorted order.
  • Time Complexity: O(n + k) (k is range of numbers)
  • Space Complexity: O(k)
  • Works only for integer values with a known range.

b. Radix Sort#

  • Sorts numbers digit by digit using counting sort as a subroutine.
  • Time Complexity: O(nk) (k is number of digits)
  • Space Complexity: O(n + k)
  • Works well for fixed-size numbers like integers.

c. Bucket Sort#

  • Divides elements into buckets and sorts each bucket individually.
  • Time Complexity: O(n + k) (depends on bucket distribution)
  • Space Complexity: O(n + k)
  • Works well for uniformly distributed data.

3. Hybrid Sorting Algorithms#

These algorithms combine multiple sorting techniques.

a. Tim Sort#

  • Combination of Merge Sort and Insertion Sort.
  • Used in Python’s built-in sorting (sorted() and .sort()).
  • Time Complexity: O(n log n)
  • Space Complexity: O(n)

b. Introsort#

  • Hybrid of Quick Sort, Heap Sort, and Insertion Sort.
  • Used in C++ STL sort().
  • Time Complexity: O(n log n)
  • Space Complexity: O(log n)

Choosing the Right Sorting Algorithm#

Algorithm Best Case Worst Case Average Case Space Complexity Stable?
Bubble Sort O(n) O(n²) O(n²) O(1) Yes
Selection Sort O(n²) O(n²) O(n²) O(1) No
Insertion Sort O(n) O(n²) O(n²) O(1) Yes
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes
Quick Sort O(n log n) O(n²) O(n log n) O(log n) No
Heap Sort O(n log n) O(n log n) O(n log n) O(1) No
Counting Sort O(n + k) O(n + k) O(n + k) O(k) Yes
Radix Sort O(nk) O(nk) O(nk) O(n + k) Yes
Bucket Sort O(n + k) O(n²) O(n) O(n + k) Yes
Tim Sort O(n) O(n log n) O(n log n) O(n) Yes