import java.util.*;

class Person {
    String name;
    int poolNoodleLength;

    Person(String name, int poolNoodleLength) {
        this.name = name;
        this.poolNoodleLength = poolNoodleLength;
    }

    @Override
    public String toString() {
        return name + ": " + poolNoodleLength;
    }
}

public class Main {
    public static void main(String[] args) {
        List<Person> people = new ArrayList<>(Arrays.asList(
            new Person("Lifeguard", 6),
            new Person("Dolphin-Man", 11),
            new Person("Sandcastle Kid", 12),
            new Person("Surfer", 14),
            new Person("Volleyball Teach", 9),
            new Person("M-A-T-I", 10),
            new Person("Runner", 7),
            new Person("Rapper", 8),
            new Person("Volleyball Boy", 13),
            new Person("Beatboxer", 4),
            new Person("Corn Oil Salesman", 5),
            new Person("Scuba Diver", 3),
            new Person("Karen", 1),
            new Person("Announcer", 2)
        ));

        long startTime = System.nanoTime();
        insertionSort(people);
        long endTime = System.nanoTime();

        long duration = (endTime - startTime);
        System.out.println("Time taken to sort: " + duration + " nanoseconds");

        for (Person person : people) {
            System.out.println(person);
        }
    }

    public static <T extends Comparable<T>> void insertionSort(List<T> list) {
        for (int i = 1; i < list.size(); i++) {
            T key = list.get(i);
            int j = i - 1;

            while (j >= 0 && list.get(j).compareTo(key) > 0) {
                list.set(j + 1, list.get(j));
                j = j - 1;
            }
            list.set(j + 1, key);
        }
    }
}

Main.main(null);

import java.util.ArrayList;
import java.util.Collections;

class Collectable {
    // Shuffle method
    public static <T> void shuffle(ArrayList<T> list) {
        Collections.shuffle(list);
    }
}

// Person class implementing Comparable
class Person implements Comparable<Person> {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    // CompareTo method for sorting by age
    @Override
    public int compareTo(Person otherPerson) {
        return Integer.compare(this.age, otherPerson.age);
    }

    // CompareTo method for sorting by name
    public int compareByName(Person otherPerson) {
        return this.name.compareTo(otherPerson.name);
    }

    // ToString method
    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

public class SuperSorting {



    public static ArrayList<Person> mergeSortReal(ArrayList<Person> list) {
        mergeSortRecursive(list, 0, list.size() - 1);
        return list;
    }

    // Merge Sort
    public static long mergeSort(ArrayList<Person> list) {
        long startTime = System.nanoTime();
        mergeSortRecursive(list, 0, list.size() - 1);
        long endTime = System.nanoTime();
        return endTime - startTime;
    }

    private static void mergeSortRecursive(ArrayList<Person> list, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSortRecursive(list, left, mid);
            mergeSortRecursive(list, mid + 1, right);
            merge(list, left, mid, right);
        }
    }

    private static void merge(ArrayList<Person> list, int left, int mid, int right) {
        ArrayList<Person> temp = new ArrayList<>();
        int i = left, j = mid + 1;

        while (i <= mid && j <= right) {
            if (list.get(i).compareTo(list.get(j)) <= 0) {
                temp.add(list.get(i));
                i++;
            } else {
                temp.add(list.get(j));
                j++;
            }
        }

        while (i <= mid) {
            temp.add(list.get(i));
            i++;
        }

        while (j <= right) {
            temp.add(list.get(j));
            j++;
        }

        for (int k = left; k <= right; k++) {
            list.set(k, temp.get(k - left));
        }
    }

    // Bubble Sort
    public static long bubbleSort(ArrayList<Person> list) {
        long startTime = System.nanoTime();
        int n = list.size();
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (list.get(j).compareTo(list.get(j + 1)) > 0) {
                    Collections.swap(list, j, j + 1);
                }
            }
        }
        long endTime = System.nanoTime();
        return endTime - startTime;
    }

    // Selection Sort
    public static long selectionSort(ArrayList<Person> list) {
        long startTime = System.nanoTime();
        int n = list.size();
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (list.get(j).compareTo(list.get(minIndex)) < 0) {
                    minIndex = j;
                }
            }
            Collections.swap(list, i, minIndex);
        }
        long endTime = System.nanoTime();
        return endTime - startTime;
    }

    // Insertion Sort
    public static long insertionSort(ArrayList<Person> list) {
        long startTime = System.nanoTime();
        int n = list.size();
        for (int i = 1; i < n; i++) {
            Person key = list.get(i);
            int j = i - 1;
            while (j >= 0 && list.get(j).compareTo(key) > 0) {
                list.set(j + 1, list.get(j));
                j--;
            }
            list.set(j + 1, key);
        }
        long endTime = System.nanoTime();
        return endTime - startTime;
    }

    public static void main(String[] args) {
        ArrayList<Person> people = new ArrayList<>();
        // Add people with names starting from each letter of the alphabet
        for (char c = 'A'; c <= 'Z'; c++) {
            String name = String.valueOf(c);
            int age = (int) (Math.random() * 50) + 20; // Random age between 20 and 70
            people.add(new Person(name, age));
        }
        //Original list
        System.out.println("Original List: " + people);
        System.out.println("\n");

        ArrayList<Person> copy1 = new ArrayList<>(people);
        ArrayList<Person> copy2 = new ArrayList<>(people);
        ArrayList<Person> copy3 = new ArrayList<>(people);
        ArrayList<Person> copy4 = new ArrayList<>(people);


        System.out.println("Merge Sort Time: " + mergeSort(copy1) + " ns");
        System.out.println("Bubble Sort Time: " + bubbleSort(copy2) + " ns");
        System.out.println("Selection Sort Time: " + selectionSort(copy3) + " ns");
        System.out.println("Insertion Sort Time: " + insertionSort(copy4) + " ns");
        
        System.out.println("\n");
        System.out.println("Sorted Array: " + mergeSortReal(copy1));
    }
}

SuperSorting.main(null);