Insertion Sort — 504 Timeout on 100k Elements

public class InsertionSortBasic {

    public static void insertionSort(int[] numbers) {
        int arrayLength = numbers.length;

        // Start from index 1 — the first element is already 'sorted' on its own
        for (int i = 1; i < arrayLength; i++) {

            // Pick the current element to be placed in the right position
            int currentElement = numbers[i];

            // j points to the last element in the already-sorted section
            int j = i - 1;

            // Shift elements in the sorted section to the right
            // as long as they are greater than the element we're placing
            while (j >= 0 && numbers[j] > currentElement) {
                numbers[j + 1] = numbers[j]; // slide this element one spot to the right
                j--;                          // move the comparison pointer left
            }

            // Drop currentElement into the gap we just created
            numbers[j + 1] = currentElement;

            // Show the array state after each pass so you can see progress
            System.out.print("After pass " + i + ": ");
            printArray(numbers);
        }
    }

    public static void printArray(int[] numbers) {
        System.out.print("[");
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i]);
            if (i < numbers.length - 1) System.out.print(", ");
        }
        System.out.println("]");
    }

    public static void main(String[] args) {
        int[] scores = {64, 25, 12, 22, 11};

        System.out.print("Original array: ");
        printArray(scores);
        System.out.println();

        insertionSort(scores);

        System.out.println();
        System.out.print("Sorted array:   ");
        printArray(scores);
    }
}

# Python implementation
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

# Example usage
arr = [64, 25, 12, 22, 11]
insertion_sort(arr)
print(arr)  # [11, 12, 22, 25, 64]

# --- C++ implementation ---
/*
#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    insertionSort(arr, n);
    for(int i=0; i<n; i++) cout << arr[i] << " ";
    // Output: 11 12 22 25 64
    return 0;
}
*/

public class InsertionSortComplexityDemo {

    // Sorts the array and counts exactly how many comparisons were made
    public static int insertionSortWithCount(int[] numbers) {
        int comparisonCount = 0;
        int arrayLength = numbers.length;

        for (int i = 1; i < arrayLength; i++) {
            int currentElement = numbers[i];
            int j = i - 1;

            while (j >= 0 && numbers[j] > currentElement) {
                comparisonCount++; // count each time we compare two elements
                numbers[j + 1] = numbers[j];
                j--;
            }
            // This comparison failed (or j went below 0), so count it too if j >= 0
            if (j >= 0) comparisonCount++;

            numbers[j + 1] = currentElement;
        }
        return comparisonCount;
    }

    public static void main(String[] args) {
        // Best case: already sorted — O(n) behaviour
        int[] alreadySorted = {1, 2, 3, 4, 5, 6, 7, 8};
        int bestCaseComparisons = insertionSortWithCount(alreadySorted.clone());
        System.out.println("Best case (already sorted, n=8):   " + bestCaseComparisons + " comparisons");

        // Worst case: reverse sorted — O(n^2) behaviour
        int[] reverseSorted = {8, 7, 6, 5, 4, 3, 2, 1};
        int worstCaseComparisons = insertionSortWithCount(reverseSorted.clone());
        System.out.println("Worst case (reverse sorted, n=8):  " + worstCaseComparisons + " comparisons");

        // Average case: random order
        int[] randomOrder = {4, 2, 7, 1, 8, 3, 6, 5};
        int averageCaseComparisons = insertionSortWithCount(randomOrder.clone());
        System.out.println("Average case (random order, n=8):  " + averageCaseComparisons + " comparisons");

        System.out.println();
        System.out.println("Theoretical worst case n*(n-1)/2 = " + (8 * 7 / 2) + " comparisons");
    }
}

public class InsertionSortStringsAndObjects {

    // --- Sorting strings alphabetically ---
    public static void insertionSortStrings(String[] names) {
        int length = names.length;

        for (int i = 1; i < length; i++) {
            String currentName = names[i];
            int j = i - 1;

            // compareTo returns negative if currentName comes before names[j] alphabetically
            while (j >= 0 && names[j].compareTo(currentName) > 0) {
                names[j + 1] = names[j]; // shift name to the right
                j--;
            }
            names[j + 1] = currentName; // place currentName in its correct slot
        }
    }

    // --- Custom class representing a student ---
    static class Student {
        String name;
        int examScore;

        Student(String name, int examScore) {
            this.name = name;
            this.examScore = examScore;
        }

        public String toString() {
            return name + " (" + examScore + ")";
        }
    }

    // --- Sorting Student objects by exam score, ascending ---
    public static void insertionSortByScore(Student[] students) {
        int length = students.length;

        for (int i = 1; i < length; i++) {
            Student currentStudent = students[i];
            int j = i - 1;

            // Shift students with higher scores to the right
            while (j >= 0 && students[j].examScore > currentStudent.examScore) {
                students[j + 1] = students[j];
                j--;
            }
            students[j + 1] = currentStudent;
        }
    }

    public static void main(String[] args) {
        // --- String sorting demo ---
        String[] playerNames = {"Zara", "Alice", "Marcus", "Bella", "Omar"};
        System.out.println("Names before sort: " + java.util.Arrays.toString(playerNames));
        insertionSortStrings(playerNames);
        System.out.println("Names after sort:  " + java.util.Arrays.toString(playerNames));

        System.out.println();

        // --- Object sorting demo ---
        Student[] classStudents = {
            new Student("Zara",   88),
            new Student("Alice",  95),
            new Student("Marcus", 72),
            new Student("Bella",  95),  // same score as Alice — notice stable ordering!
            new Student("Omar",   60)
        };

        System.out.println("Students before sort by score:");
        for (Student s : classStudents) System.out.println("  " + s);

        insertionSortByScore(classStudents);

        System.out.println("Students after sort by score:");
        for (Student s : classStudents) System.out.println("  " + s);
    }
}

public class InsertionSortMistakes {

    // Correct implementation
    public static void insertionSortCorrect(int[] arr) {
        for (int i = 1; i < arr.length; i++) {   // start at 1
            int key = arr[i];                     // save it!
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {      // greater THAN, not >= 
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    // Wrong: start at 0
    public static void wrongStartIndex(int[] arr) {
        for (int i = 0; i < arr.length; i++) {   // BUG: i=0
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    // Wrong: using >=
    public static void wrongComparison(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] >= key) {     // BUG: >= breaks stability
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    // Wrong: missing key assignment
    public static void missingKey(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            // int key = arr[i];   // BUG: missing
            int j = i - 1;
            while (j >= 0 && arr[j] > arr[i]) {   // arr[i] changes during shifts!
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = arr[i];  // now this is corrupted
        }
    }

    public static void main(String[] args) {
        int[] correctArr = {64, 25, 12, 22, 11};
        insertionSortCorrect(correctArr);
        System.out.println("Correct: " + java.util.Arrays.toString(correctArr));

        // The other methods would cause exceptions or incorrect results
        // Uncomment to test:
        // int[] test1 = {64, 25, 12, 22, 11};
        // wrongStartIndex(test1);  // throws ArrayIndexOutOfBoundsException
    }
}

// io.thecodeforge — dsa tutorial

public class DetectNearlySortedBeforeSorting {

    // Count how many pairs are out of order to estimate inversion ratio
    public static double inversionRatio(int[] array) {
        // Only sample first 1000 elements for speed in production
        int limit = Math.min(array.length, 1000);
        int inversions = 0;
        int comparisons = 0;
        for (int i = 0; i < limit - 1; i++) {
            for (int j = i + 1; j < limit; j++) {
                comparisons++;
                if (array[i] > array[j]) inversions++;
            }
        }
        // Avoid division by zero for trivially small or empty arrays
        return comparisons == 0 ? 0.0 : (double) inversions / comparisons;
    }

    public static void main(String[] args) {
        // Simulating a nearly-sorted log file timestamps (most events in order)
        int[] logTimestamps = {100, 101, 102, 103, 104, 99, 105, 106, 107};
        double ratio = inversionRatio(logTimestamps);
        System.out.println("Inversion ratio: " + ratio);  // ~0.027 or 2.7%
        if (ratio < 0.15) {
            System.out.println("Use Insertion Sort — data is nearly sorted");
        } else {
            System.out.println("Too many inversions. Use Quicksort or TimSort");
        }
    }
}

// io.thecodeforge — dsa tutorial

// Simulating an embedded system: no external libraries, no heap, only primitive arrays
public class EmbeddedInsertionSort {

    // WARNING: For real embedded, use uint16_t and volatile. Here we simulate with Java int[]
    public static void sortSensorReadings(int[] sensorData) {
        // Insertion sort: only uses a single temp variable — no new arrays
        for (int i = 1; i < sensorData.length; i++) {
            int currentReading = sensorData[i];  // this temp is your total extra memory
            int position = i - 1;
            // Shift elements right until we find where currentReading fits
            while (position >= 0 && sensorData[position] > currentReading) {
                sensorData[position + 1] = sensorData[position];
                position--;
            }
            sensorData[position + 1] = currentReading;
        }
    }

    public static void main(String[] args) {
        // Simulating ADC readings from a temperature sensor (0-1023 range)
        int[] sensorReadings = {512, 256, 768, 128, 896};
        sortSensorReadings(sensorReadings);
        for (int val : sensorReadings) {
            System.out.print(val + " ");
        }
        System.out.println();  // Output: 128 256 512 768 896
    }
}

// io.thecodeforge — dsa tutorial

import java.util.*;
import java.util.concurrent.*;

public class ParallelLinkedListInsertionSort {

    // Node for a singly-linked list
    static class EventNode {
        int timestamp;
        EventNode next;
        EventNode(int timestamp) { this.timestamp = timestamp; }
    }

    // Standard insertion sort on a linked list chunk — O(n²) but only on small chunks
    private static EventNode insertionSortChunk(EventNode head) {
        if (head == null || head.next == null) return head;
        EventNode sorted = null;
        EventNode current = head;
        while (current != null) {
            EventNode nextEvent = current.next;
            // Insert current into sorted list via pointer manipulation
            if (sorted == null || sorted.timestamp >= current.timestamp) {
                current.next = sorted;
                sorted = current;
            } else {
                EventNode walker = sorted;
                while (walker.next != null && walker.next.timestamp < current.timestamp) {
                    walker = walker.next;
                }
                current.next = walker.next;
                walker.next = current;
            }
            current = nextEvent;
        }
        return sorted;
    }

    // Split list into k chunks, sort each in parallel, then merge
    public static EventNode parallelSort(EventNode head, int threadCount) {
        if (head == null || head.next == null) return head;
        // Step 1: Split into k chunks of roughly equal size
        int totalSize = 0;
        EventNode counter = head;
        while (counter != null) { totalSize++; counter = counter.next; }
        int chunkSize = (totalSize + threadCount - 1) / threadCount;
        List<EventNode> chunks = new ArrayList<>();
        EventNode current = head;
        for (int i = 0; i < threadCount && current != null; i++) {
            chunks.add(current);
            EventNode prev = null;
            for (int j = 0; j < chunkSize && current != null; j++) {
                prev = current;
                current = current.next;
            }
            if (prev != null) prev.next = null;  // sever the chunk
        }
        // Step 2: Sort each chunk in parallel
        ExecutorService pool = Executors.newFixedThreadPool(threadCount);
        List<Future<EventNode>> futures = new ArrayList<>();
        for (EventNode chunk : chunks) {
            futures.add(pool.submit(() -> insertionSortChunk(chunk)));
        }
        List<EventNode> sortedChunks = new ArrayList<>();
        try {
            for (Future<EventNode> f : futures) sortedChunks.add(f.get());
        } catch (Exception e) { throw new RuntimeException(e); }
        pool.shutdown();
        // Step 3: Merge sorted chunks using a min-heap
        PriorityQueue<EventNode> heap = new PriorityQueue<>(Comparator.comparingInt(n -> n.timestamp));
        for (EventNode chunk : sortedChunks) {
            if (chunk != null) heap.add(chunk);
        }
        EventNode dummy = new EventNode(0);
        EventNode tail = dummy;
        while (!heap.isEmpty()) {
            EventNode smallest = heap.poll();
            tail.next = smallest;
            tail = smallest;
            if (smallest.next != null) heap.add(smallest.next);
        }
        dummy.next = null;  // isolate dummy
        return tail;  // return head of merged list
    }

    public static void main(String[] args) {
        // Simulating a stream of 100 unordered events (timestamps)
        EventNode head = new EventNode(5);
        EventNode current = head;
        Random rand = new Random(42);
        for (int i = 0; i < 99; i++) {
            current.next = new EventNode(rand.nextInt(100));
            current = current.next;
        }
        EventNode sorted = parallelSort(head, 4);  // 4-core CPU
        // Print first 10 to verify order
        for (int i = 0; i < 10 && sorted != null; i++) {
            System.out.print(sorted.timestamp + " ");
            sorted = sorted.next;
        }
        System.out.println("...");
    }
}