Compare sorting algorithms

🔹 Sorting Algorithms Comparison

Algorithm	Best Case	Average Case	Worst Case	Space	Stable?	Notes / When to Use
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Educational, rarely used in practice.
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Good for small n or nearly sorted data.
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No	Simple but inefficient.
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	Good general-purpose; stable.
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No	Fast in practice, used widely; worst-case avoided with randomization/pivoting.
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No	Good worst-case guarantees, but slower constants than quicksort.
Counting Sort	O(n + k)	O(n + k)	O(n + k)	O(n + k)	Yes	Works only with integers in small range k.
Radix Sort	O(n·k)	O(n·k)	O(n·k)	O(n + k)	Yes	Digit-based sort; good for integers/strings.
Bucket Sort	O(n + k)	O(n + k)	O(n²)	O(n + k)	Depends	Works if input is uniformly distributed.
Shell Sort	O(n log n)	O(n^(3/2))	O(n²)	O(1)	No	Improved insertion sort with gap sequence.
Timsort (Python’s sort)	O(n)	O(n log n)	O(n log n)	O(n)	Yes	Hybrid of merge + insertion sort, optimized for real-world data.

# Sorting Algorithms Comparison with Python Implementations
 
# -------------------------------
# Bubble Sort
# -------------------------------
# Time: Best O(n), Avg O(n^2), Worst O(n^2)
# Space: O(1), Stable
 
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr
 
 
# -------------------------------
# Insertion Sort
# -------------------------------
# Time: Best O(n), Avg O(n^2), Worst O(n^2)
# Space: O(1), Stable
 
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr
 
 
# -------------------------------
# Selection Sort
# -------------------------------
# Time: Best O(n^2), Avg O(n^2), Worst O(n^2)
# Space: O(1), Not Stable
 
def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr
 
 
# -------------------------------
# Merge Sort
# -------------------------------
# Time: Best O(n log n), Avg O(n log n), Worst O(n log n)
# Space: O(n), Stable
 
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr)//2
    L = merge_sort(arr[:mid])
    R = merge_sort(arr[mid:])
    res = []
    i = j = 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            res.append(L[i])
            i += 1
        else:
            res.append(R[j])
            j += 1
    res.extend(L[i:])
    res.extend(R[j:])
    return res
 
 
# -------------------------------
# Quick Sort
# -------------------------------
# Time: Best O(n log n), Avg O(n log n), Worst O(n^2)
# Space: O(log n), Not Stable
 
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + mid + quick_sort(right)
 
 
# -------------------------------
# Heap Sort
# -------------------------------
# Time: Best O(n log n), Avg O(n log n), Worst O(n log n)
# Space: O(1), Not Stable
import heapq
 
def heap_sort(arr):
    h = []
    for v in arr:
        heapq.heappush(h, v)
    return [heapq.heappop(h) for _ in range(len(h))]
 
 
# -------------------------------
# Counting Sort
# -------------------------------
# Time: Best O(n+k), Avg O(n+k), Worst O(n+k)
# Space: O(n+k), Stable
# Only works for non-negative integers with limited range
 
def counting_sort(arr):
    k = max(arr) + 1
    count = [0] * k
    for x in arr:
        count[x] += 1
    res = []
    for i, c in enumerate(count):
        res.extend([i] * c)
    return res
 
 
# -------------------------------
# Radix Sort (LSD, base 10)
# -------------------------------
# Time: O(n * k), where k = number of digits
# Space: O(n + k), Stable
 
def counting_sort_exp(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
 
    for i in arr:
        idx = (i // exp) % 10
        count[idx] += 1
 
    for i in range(1, 10):
        count[i] += count[i-1]
 
    for i in range(n-1, -1, -1):
        idx = (arr[i] // exp) % 10
        output[count[idx]-1] = arr[i]
        count[idx] -= 1
 
    return output
 
def radix_sort(arr):
    max_num = max(arr)
    exp = 1
    res = arr[:]
    while max_num // exp > 0:
        res = counting_sort_exp(res, exp)
        exp *= 10
    return res
 
 
# -------------------------------
# Bucket Sort
# -------------------------------
# Time: Best O(n+k), Avg O(n+k), Worst O(n^2)
# Space: O(n+k), Depends on sort used in buckets
# Works best for uniformly distributed floats in [0,1)
 
def bucket_sort(arr):
    n = len(arr)
    buckets = [[] for _ in range(n)]
 
    for x in arr:
        idx = int(n * x)
        buckets[idx].append(x)
 
    for i in range(n):
        buckets[i] = insertion_sort(buckets[i])
 
    res = []
    for b in buckets:
        res.extend(b)
    return res
 
 
# -------------------------------
# Shell Sort
# -------------------------------
# Time: Best O(n log n), Avg O(n^(3/2)), Worst O(n^2)
# Space: O(1), Not Stable
 
def shell_sort(arr):
	n = len(arr)
	gap = n // 2
	while gap > 0:
		for i in range(gap, n):
			temp = arr[i]
			j = i
			while j >= gap and arr[j-gap] > temp:
				arr[j] = arr[j-gap]
				j -= gap
			arr[j] = temp
		gap //= 2
	return arr
 
 
# -------------------------------
# Timsort (Python built-in)
# -------------------------------
# Time: Best O(n), Avg O(n log n), Worst O(n log n)
# Space: O(n), Stable
# Directly available as list.sort() or sorted()
 
def timsort_example(arr):
	return sorted(arr) # Python uses Timsort internally