/**
 * Book object with a title and publication year. This class implements
 * Comparable to allow sorting based on the publication year.
 * 
 * @author Alexander Ricciardi
 * @version 1.0
 * @date 07/14/2024
 */
class Book implements Comparable {
    String title;
    int year;

    /**
     * Constructs a new Book object.
     *
     * @param title The title of the book.
     * @param year  The year the book was published.
     */
    public Book(String title, int year) {
    this.title = title;
    this.year = year;
    }

    /**
     * Compares this book with another book based on the publication year.
     *
     * @param other The book to compare with.
     * @return A negative integer, zero, or a positive integer as this book is less
     *         than, equal to, or greater than the specified book.
     */
    @Override
    public int compareTo(Book other) {
    return Integer.compare(this.year, other.year);
    }

    /**
     * Returns a string representation of the book.
     *
     * @return A string in the format "title (year)".
     */
    @Override
    public String toString() {
    return title + " (" + year + ")";
    }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Sorts and search a list of books. It implements merge sort for sorting and
 * binary search for searching.
 * 
 * @author Alexander Ricciardi
 * @version 1.0
 * @date 07/14/2024
 */
public class BookSortingSearching {

    /**
     * The main method that demonstrates sorting and searching on a list of books.
     *
     * @param args Command line arguments (not used).
     */
    public static void main(String[] args) {
    // Initialize the list of books
    ArrayList books = new ArrayList<>(
        Arrays.asList(
                     new Book("To Kill a Mockingbird", 1960), 
                     new Book("1984", 1949),
                     new Book("The Great Gatsby", 1925),
                     new Book("One Hundred Years of Solitude", 1967),
                     new Book("The Catcher in the Rye", 1951), 
                     new Book("Brave New World", 1932),
                     new Book("The Hobbit", 1937), 
                     new Book("The Lord of the Rings", 1954),
                     new Book("Pride and Prejudice", 1813), 
                     new Book("Animal Farm", 1945)
                 ));

    // Print the original list
    System.out.println("Original list:");
    books.forEach(System.out::println);

    // Sort the books using merge sort
    mergeSort(books, 0, books.size() - 1);

    // Print the sorted list
    System.out.println("\nSorted list by year:");
    books.forEach(System.out::println);

    // Perform binary search based on user input
    Scanner scn = new Scanner(System.in);
    System.out.print("\nEnter a year to search for: ");
    int searchYear = scn.nextInt();

    int result = binarySearch(books, searchYear);
    if (result != -1) {
        System.out.println("Book found: " + books.get(result));
    } else {
        System.out.println("No book found for the year " + searchYear);
    }
    scn.close();
    }

    /**
     * Sorts the given list of books using the merge sort algorithm.
     *
     * @param books The list of books to sort.
     * @param left  The starting index of the subarray to sort.
     * @param right The ending index of the subarray to sort.
     */
    private static void mergeSort(ArrayList books, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(books, left, mid); // Sort left half
        mergeSort(books, mid + 1, right); // Sort right half
        merge(books, left, mid, right); // Merge the sorted halves
    }
    }

    /**
     * Merges two sorted subarrays of the books list.
     *
     * @param books The list of books containing the subarrays to merge.
     * @param left  The starting index of the left subarray.
     * @param mid   The ending index of the left subarray.
     * @param right The ending index of the right subarray.
     */
    private static void merge(ArrayList books, int left, int mid, int right) {
    // Create temporary arrays
    ArrayList leftList = new ArrayList<>(books.subList(left, mid + 1));
    ArrayList rightList = new ArrayList<>(books.subList(mid + 1, right + 1));

    int i = 0, j = 0, k = left;

    // Merge the two lists
    while (i < leftList.size() && j < rightList.size()) {
        if (leftList.get(i).compareTo(rightList.get(j)) <= 0) {
        books.set(k++, leftList.get(i++));
        } else {
        books.set(k++, rightList.get(j++));
        }
    }

    // Copy remaining elements of leftList, if any
    while (i < leftList.size()) {
        books.set(k++, leftList.get(i++));
    }

    // Copy remaining elements of rightList, if any
    while (j < rightList.size()) {
        books.set(k++, rightList.get(j++));
    }
    }

    /**
     * Performs a binary search on the sorted list of books to find a book by its
     * publication year.
     *
     * @param books The sorted list of books to search.
     * @param year  The publication year to search for.
     * @return The index of the book if found, -1 otherwise.
     */
    private static int binarySearch(ArrayList books, int year) {
    int left = 0, right = books.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (books.get(mid).year == year) {
        return mid; // Book found
        }
        if (books.get(mid).year < year) {
        left = mid + 1; // Search in the right half
        } else {
        right = mid - 1; // Search in the left half
        }
    }
    return -1; // Book not found
    }
}

To Kill a Mockingbird (1960)
1984 (1949)
The Great Gatsby (1925)
One Hundred Years of Solitude (1967)
The Catcher in the Rye (1951)
Brave New World (1932)
The Hobbit (1937)
The Lord of the Rings (1954)
Pride and Prejudice (1813)
Animal Farm (1945)

Sorted list by year:
Pride and Prejudice (1813)
The Great Gatsby (1925)
Brave New World (1932)
The Hobbit (1937)
Animal Farm (1945)
1984 (1949)
The Catcher in the Rye (1951)
The Lord of the Rings (1954)
To Kill a Mockingbird (1960)
One Hundred Years of Solitude (1967)

Enter a year to search for: 1951
Book found: The Catcher in the Rye (1951)