def bubble_sort_basic(arr):
    """
    Basic bubble sort - always does n-1 passes
    Time Complexity: O(n²) - always
    Space Complexity: O(1)
    """
    n = len(arr)
 
    # Traverse through all array elements
    for i in range(n - 1):
        # Last i elements are already in place
        for j in range(n - i - 1):
            # Traverse the array from 0 to n-i-1
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
 
    return arr
 
# Example usage
arr = [64, 34, 25, 12, 22, 11, 90]
print("Original array:", arr)
sorted_arr = bubble_sort_basic(arr.copy())
print("Sorted array:", sorted_arr)

def bubble_sort_optimized(arr):
    """
    Optimized bubble sort - stops early if array becomes sorted
    Best case: O(n) when array is already sorted
    Worst case: O(n²)
    """
    n = len(arr)
 
    for i in range(n - 1):
        swapped = False  # Flag to check if any swapping happened
 
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
 
        # If no swapping happened, array is sorted
        if not swapped:
            break
 
    return arr

def selection_sort(arr):
    """
    Selection sort implementation
    Time Complexity: O(n²) - always
    Space Complexity: O(1)
    """
    n = len(arr)
 
    # Traverse through all array elements
    for i in range(n - 1):
        # Find the minimum element in remaining unsorted array
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
 
        # Swap the found minimum element with the first element
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
 
    return arr
 
# Example usage
arr = [64, 25, 12, 22, 11]
print("Original array:", arr)
sorted_arr = selection_sort(arr.copy())
print("Sorted array:", sorted_arr)

def selection_sort_verbose(arr):
    """Selection sort with detailed output"""
    n = len(arr)
    print(f"Starting array: {arr}")
 
    for i in range(n - 1):
        min_idx = i
        print(f"\nPass {i + 1}: Finding minimum from index {i}")
 
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
                print(f"  New minimum found: {arr[min_idx]} at index {min_idx}")
 
        if min_idx != i:
            print(f"  Swapping {arr[i]} and {arr[min_idx]}")
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
        else:
            print(f"  {arr[i]} is already in correct position")
 
        print(f"  Array after pass {i + 1}: {arr}")
 
    return arr

def insertion_sort(arr):
    """
    Insertion sort implementation
    Time Complexity: Best O(n), Average/Worst O(n²)
    Space Complexity: O(1)
    """
    # Traverse from 1 to len(arr)
    for i in range(1, len(arr)):
        key = arr[i]  # Current element to be inserted
        j = i - 1     # Index of the last element in sorted portion
 
        # Move elements greater than key one position ahead
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
 
        # Place key at its correct position
        arr[j + 1] = key
 
    return arr
 
# Example usage
arr = [12, 11, 13, 5, 6]
print("Original array:", arr)
sorted_arr = insertion_sort(arr.copy())
print("Sorted array:", sorted_arr)

def binary_search_insertion_sort(arr):
    """
    Insertion sort with binary search to find insertion position
    Reduces comparisons but shifting still takes O(n) time
    """
    def binary_search(arr, val, start, end):
        if start == end:
            return start if arr[start] > val else start + 1
 
        if start > end:
            return start
 
        mid = (start + end) // 2
 
        if arr[mid] < val:
            return binary_search(arr, val, mid + 1, end)
        elif arr[mid] > val:
            return binary_search(arr, val, start, mid - 1)
        else:
            return mid
 
    for i in range(1, len(arr)):
        key = arr[i]
        j = binary_search(arr, key, 0, i - 1)
 
        # Shift elements to make space
        arr[j + 1:i + 1] = arr[j:i]
        arr[j] = key
 
    return arr

def merge_sort(arr):
    """
    Merge sort implementation using recursion
    Time Complexity: O(n log n) - always
    Space Complexity: O(n)
    """
    # Base case: arrays with 0 or 1 element are already sorted
    if len(arr) <= 1:
        return arr
 
    # Divide the array into two halves
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
 
    # Recursively sort both halves
    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)
 
    # Merge the sorted halves
    return merge(left_sorted, right_sorted)
 
def merge(left, right):
    """
    Merge two sorted arrays into one sorted array
    """
    result = []
    i = j = 0
 
    # Compare elements from both arrays and add smaller one to result
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
 
    # Add remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
 
    return result
 
# Example usage
arr = [38, 27, 43, 3, 9, 82, 10]
print("Original array:", arr)
sorted_arr = merge_sort(arr)
print("Sorted array:", sorted_arr)

def merge_sort_inplace(arr, left=0, right=None):
    """
    In-place merge sort (modifies original array)
    Slightly more memory efficient
    """
    if right is None:
        right = len(arr) - 1
 
    if left < right:
        mid = (left + right) // 2
 
        # Sort first and second halves
        merge_sort_inplace(arr, left, mid)
        merge_sort_inplace(arr, mid + 1, right)
 
        # Merge the sorted halves
        merge_inplace(arr, left, mid, right)
 
def merge_inplace(arr, left, mid, right):
    """Merge function for in-place merge sort"""
    # Create temporary arrays for left and right subarrays
    left_arr = arr[left:mid + 1]
    right_arr = arr[mid + 1:right + 1]
 
    i = j = 0
    k = left
 
    # Merge the temporary arrays back into arr[left..right]
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] <= right_arr[j]:
            arr[k] = left_arr[i]
            i += 1
        else:
            arr[k] = right_arr[j]
            j += 1
        k += 1
 
#### Iterative Version (Bottom-Up Approach)
```python copy
def merge_sort_iterative(arr):
    """
    Iterative merge sort implementation (bottom-up)
    Avoids recursion overhead
    """
    if len(arr) <= 1:
        return arr
 
    # Make a copy to avoid modifying original
    arr = arr.copy()
    n = len(arr)
 
    # Start with subarrays of size 1, then 2, 4, 8, etc.
    size = 1
    while size < n:
        # Pick starting point of left sub array
        left = 0
        while left < n - 1:
            # Calculate mid and right points
            mid = min(left + size - 1, n - 1)
            right = min(left + size * 2 - 1, n - 1)
 
            # Merge subarrays arr[left...mid] and arr[mid+1...right]
            if mid < right:
                merge_iterative(arr, left, mid, right)
 
            left = left + size * 2
 
        size *= 2
 
    return arr
 
def merge_iterative(arr, left, mid, right):
    """Helper function for iterative merge sort"""
    # Create temporary arrays
    left_arr = arr[left:mid + 1]
    right_arr = arr[mid + 1:right + 1]
 
    i = j = 0
    k = left
 
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] <= right_arr[j]:
            arr[k] = left_arr[i]
            i += 1
        else:
            arr[k] = right_arr[j]
            j += 1
        k += 1
 
    while i < len(left_arr):
        arr[k] = left_arr[i]
        i += 1
        k += 1
 
    while j < len(right_arr):
        arr[k] = right_arr[j]
        j += 1
        k += 1

def quick_sort(arr, low=0, high=None):
    """
    Quick sort implementation with last element as pivot
    Time Complexity: Best/Average O(n log n), Worst O(n²)
    Space Complexity: O(log n) average, O(n) worst case
    """
    if high is None:
        high = len(arr) - 1
 
    if low < high:
        # Partition the array and get pivot index
        pivot_index = partition(arr, low, high)
 
        # Recursively sort elements before and after partition
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)
 
def partition(arr, low, high):
    """
    Lomuto partition scheme
    Takes last element as pivot, places it at correct position,
    and places all smaller elements to left, all greater to right
    """
    # Choose rightmost element as pivot
    pivot = arr[high]
 
    # Index of smaller element (indicates right position of pivot)
    i = low - 1
 
    for j in range(low, high):
        # If current element is smaller than or equal to pivot
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
 
    # Place pivot at correct position
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1
 
# Example usage
arr = [10, 7, 8, 9, 1, 5]
print("Original array:", arr)
quick_sort(arr)
print("Sorted array:", arr)

def quick_sort_hoare(arr, low=0, high=None):
    """Quick sort with Hoare partition scheme"""
    if high is None:
        high = len(arr) - 1
 
    if low < high:
        pivot_index = hoare_partition(arr, low, high)
        quick_sort_hoare(arr, low, pivot_index)
        quick_sort_hoare(arr, pivot_index + 1, high)
 
def hoare_partition(arr, low, high):
    """
    Hoare partition scheme
    More efficient than Lomuto as it does fewer swaps
    """
    pivot = arr[low]  # Choose first element as pivot
    i = low - 1
    j = high + 1
 
    while True:
        # Find element greater than pivot from left
        i += 1
        while arr[i] < pivot:
            i += 1
 
        # Find element smaller than pivot from right
        j -= 1
        while arr[j] > pivot:
            j -= 1
 
        # If pointers crossed, partitioning is done
        if i >= j:
            return j
 
        # Swap elements
        arr[i], arr[j] = arr[j], arr[i]

import random
 
def randomized_quick_sort(arr, low=0, high=None):
    """
    Randomized quick sort - chooses random pivot
    Helps avoid worst-case O(n²) performance on sorted/reverse sorted arrays
    """
    if high is None:
        high = len(arr) - 1
 
    if low < high:
        # Randomly choose pivot and swap with last element
        random_index = random.randint(low, high)
        arr[random_index], arr[high] = arr[high], arr[random_index]
 
        # Use regular partition
        pivot_index = partition(arr, low, high)
        randomized_quick_sort(arr, low, pivot_index - 1)
        randomized_quick_sort(arr, pivot_index + 1, high)

def quick_sort_median_of_three(arr, low=0, high=None):
    """Quick sort with median-of-three pivot selection"""
    if high is None:
        high = len(arr) - 1
 
    if low < high:
        # Choose median of first, middle, and last elements as pivot
        median_of_three(arr, low, high)
 
        pivot_index = partition(arr, low, high)
        quick_sort_median_of_three(arr, low, pivot_index - 1)
        quick_sort_median_of_three(arr, pivot_index + 1, high)
 
def median_of_three(arr, low, high):
    """
    Choose median of three elements and place it at the end
    Helps improve performance on partially sorted arrays
    """
    mid = (low + high) // 2
 
    # Sort the three elements
    if arr[mid] < arr[low]:
        arr[low], arr[mid] = arr[mid], arr[low]
    if arr[high] < arr[low]:
        arr[low], arr[high] = arr[high], arr[low]
    if arr[high] < arr[mid]:
        arr[mid], arr[high] = arr[high], arr[mid]
 
    # Place median at the end (will be used as pivot)
    arr[mid], arr[high] = arr[high], arr[mid]

def quick_sort_iterative(arr):
    """
    Iterative implementation of quick sort
    Uses explicit stack instead of recursion
    """
    if len(arr) <= 1:
        return arr
 
    # Create stack and push initial values
    stack = [(0, len(arr) - 1)]
 
    while stack:
        low, high = stack.pop()
 
        if low < high:
            # Partition and get pivot index
            pivot_index = partition(arr, low, high)
 
            # Push left and right subarrays to stack
            stack.append((low, pivot_index - 1))
            stack.append((pivot_index + 1, high))
 
    return arr

def hybrid_sort(arr, threshold=10):
    """
    Hybrid sorting algorithm:
    - Use Quick Sort for large arrays
    - Use Insertion Sort for small arrays (more efficient due to lower overhead)
    """
    if len(arr) <= threshold:
        return insertion_sort(arr)
    else:
        quick_sort(arr)
        return arr

def quick_sort_tail_optimized(arr, low=0, high=None):
    """
    Quick sort with tail recursion optimization
    Reduces space complexity in worst case
    """
    if high is None:
        high = len(arr) - 1
 
    while low < high:
        pivot_index = partition(arr, low, high)
 
        # Recur on smaller subarray to optimize space
        if pivot_index - low < high - pivot_index:
            quick_sort_tail_optimized(arr, low, pivot_index - 1)
            low = pivot_index + 1
        else:
            quick_sort_tail_optimized(arr, pivot_index + 1, high)
            high = pivot_index - 1

import random
import time
 
def test_sorting_algorithm(sort_func, arr_size=1000, num_tests=5):
    """Test sorting algorithm with random data"""
    print(f"\nTesting {sort_func.__name__}:")
 
    total_time = 0
    for i in range(num_tests):
        # Generate random array
        test_arr = [random.randint(1, 1000) for _ in range(arr_size)]
        original = test_arr.copy()
 
        # Time the sorting
        start_time = time.time()
        if sort_func.__name__.startswith('quick_sort'):
            sort_func(test_arr)
        else:
            test_arr = sort_func(test_arr)
        end_time = time.time()
 
        # Verify correctness
        assert test_arr == sorted(original), "Sorting failed!"
 
        total_time += (end_time - start_time)
 
    avg_time = total_time / num_tests
    print(f"Average time for {arr_size} elements: {avg_time:.4f} seconds")
 
# Example usage
if __name__ == "__main__":
    # Test all algorithms
    algorithms = [
        bubble_sort_optimized,
        selection_sort,
        insertion_sort,
        merge_sort,
        lambda arr: quick_sort(arr.copy()) or arr
    ]
 
    for algorithm in algorithms:
        test_sorting_algorithm(algorithm, arr_size=1000)