SortAndSearch.java

import java.util.ArrayList;

/**
 * Provides functions to search and sort a generic list of comparable elements.
 * @author Showmick Das
 * @version 1.0
 */
public class SortAndSearch {

    /**
     * Sorts the given list using merge sort.
     * This method sorts the list in place.
     * @param <T>  Type of objects in the list
     * @param list List of objects to sort
     */
    public static <T extends Comparable<T>> void mergeSort(ArrayList<T> list) {
        if (list.size() <= 1) {
            return;
        }
        int mid = list.size() / 2;
        ArrayList<T> left = new ArrayList<T>();
        ArrayList<T> right = new ArrayList<T>();

        for (int i = 0; i < mid; i++) {
            left.add(list.get(i));
        }
        for (int i = mid; i < list.size(); i++) {
            right.add(list.get(i));
        }
        mergeSort(left);
        mergeSort(right);
        merge(list, left, right);
    }

    /**
     * Helper method to merge two sorted lists into the original list.
     * @param <T>   Type of objects in the list
     * @param list  The original list to hold the merged result
     * @param left  Left sublist (sorted)
     * @param right Right sublist (sorted)
     */
    private static <T extends Comparable<T>> void merge(ArrayList<T> list, ArrayList<T> left, ArrayList<T> right) {
        int i = 0, j = 0, k = 0;
        while (i < left.size() && j < right.size()) {
            if (left.get(i).compareTo(right.get(j)) <= 0) {
                list.set(k++, left.get(i++));
            } else {
                list.set(k++, right.get(j++));
            }
        }
        while (i < left.size()) {
            list.set(k++, left.get(i++));
        }
        while (j < right.size()) {
            list.set(k++, right.get(j++));
        }
    }

    /**
     * Sorts the given list using insertion sort.
     * This method sorts the list in place.
     * @param <T>  Type of objects in the list
     * @param list List of objects to sort
     */
    public static <T extends Comparable<T>> void insertionSort(ArrayList<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--;
            }
            list.set(j + 1, key);
        }
    }

    /**
     * Searches the given list for the given element using binary search, assuming the list is
     * sorted.
     * @param <T> Type of objects in the list
     * @param list List of objects to search within
     * @param toFind The element to find in the list
     * @return The index at which the given element exists in the list, or -1 if it is not present
     */
    public static <T extends Comparable<T>> int binarySearch(ArrayList<T> list, T toFind) {
        int left = 0;
        int right = list.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            T midElement = list.get(mid);
            int cmp = midElement.compareTo(toFind);
            if (cmp == 0) {
                return mid;
            } else if (cmp < 0) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}