Insertion sort cost

def insertion_sort(arr):
    """
    Insertion Sort - Insert each element into sorted portion
    
    Time Complexity:
    - Best Case: O(n) - already sorted
    - Average Case: O(n²)
    - Worst Case: O(n²) - reverse sorted
    
    Space Complexity: O(1) - in-place sorting
    
    Properties:
    - Stable (preserves order of equal elements)
    - Adaptive (fast for nearly-sorted data)
    - In-place (O(1) extra space)
    - Online (can sort as data arrives)
    """
    n = len(arr)
    
    # Start from second element (first is "sorted")
    for i in range(1, n):
        # Element to be inserted
        key = arr[i]
        
        # Position in sorted portion to compare with
        j = i - 1
        
        # Move elements greater than key one position right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        # Insert key in correct position
        arr[j + 1] = key
    
    return arr


# Example Usage
arr = [12, 11, 13, 5, 6]
print(f"Original: {arr}")

sorted_arr = insertion_sort(arr.copy())
print(f"Sorted: {sorted_arr}")

# Output:
# Original: [12, 11, 13, 5, 6]
# Sorted: [5, 6, 11, 12, 13]


# Demonstrating best case (already sorted)
sorted_arr = [1, 2, 3, 4, 5]
insertion_sort(sorted_arr)  # O(n) - only n comparisons!
print(f"Already sorted: {sorted_arr}")
# Output: Already sorted: [1, 2, 3, 4, 5]


# Binary insertion variant: fewer comparisons, same number of shifts
def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        low, high = 0, i
        # Upper bound keeps equal keys in their original order.
        while low < high:
            middle = low + (high - low) // 2
            if key < arr[middle]:
                high = middle
            else:
                low = middle + 1
        for j in range(i, low, -1):
            arr[j] = arr[j - 1]
        arr[low] = key
    return arr

public class InsertionSort {
    /**
     * Insertion Sort - Insert each element into sorted portion
     * 
     * Time Complexity:
     * - Best Case: O(n) - already sorted
     * - Average Case: O(n²)
     * - Worst Case: O(n²) - reverse sorted
     * 
     * Space Complexity: O(1) - in-place sorting
     */
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        
        // Start from second element (first is "sorted")
        for (int i = 1; i < n; i++) {
            // Element to be inserted
            int key = arr[i];
            
            // Position in sorted portion to compare with
            int j = i - 1;
            
            // Move elements greater than key one position right
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            
            // Insert key in correct position
            arr[j + 1] = key;
        }
    }

    // Binary insertion: O(log n) comparisons per item, but still O(n²) shifts.
    public static void binaryInsertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int low = 0;
            int high = i;
            // Upper bound preserves the order of equal keys.
            while (low < high) {
                int middle = low + (high - low) / 2;
                if (key < arr[middle]) high = middle;
                else low = middle + 1;
            }
            for (int j = i; j > low; j--) {
                arr[j] = arr[j - 1];
            }
            arr[low] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        System.out.println("Original: " + java.util.Arrays.toString(arr));
        
        insertionSort(arr);
        
        System.out.println("Sorted: " + java.util.Arrays.toString(arr));
    }
}