CS 3304 - U2.java

import java.util.Arrays;
import java.util.Random;

/**
 * SortAlgorithms - A comprehensive implementation and comparison of sorting algorithms
 * 
 * This code demonstrates two fundamental divide-and-conquer sorting algorithms:
 * - Merge Sort: Stable, O(n log n) time complexity, O(n) space complexity
 * - Quick Sort: In-place, average O(n log n), worst-case O(n^2) time complexity
 * 
 * Both algorithms are benchmarked against different dataset sizes to analyze performance.
 */
public class SortAlgorithms {

    /**
     * Merge Sort - A stable, divide-and-conquer sorting algorithm
     * 
     * Time Complexity: O(n log n) in all cases (best, average, worst)
     * Space Complexity: O(n) due to temporary arrays
     * Stability: Stable (maintains relative order of equal elements)
     * 
     * Algorithm Steps:
     * 1. Divide the array into two halves
     * 2. Recursively sort both halves
     * 3. Merge the sorted halves back together
     * 
     * @param array The integer array to be sorted (modified in-place)
     */
    public static void mergeSort(int[] array) {
        // Base case: arrays with 0 or 1 element are already sorted
        if (array.length > 1) {
            // Find the middle point to divide the array into two halves
            int mid = array.length / 2;
            
            // Create left and right subarrays
            int[] left = Arrays.copyOfRange(array, 0, mid);
            int[] right = Arrays.copyOfRange(array, mid, array.length);
            
            // Recursively sort both halves
            mergeSort(left);
            mergeSort(right);
            
            // Merge the sorted halves back into the original array
            merge(array, left, right);
        }
    }

    /**
     * Merge - Helper method to combine two sorted arrays into one sorted array
     * 
     * This method performs the "conquer" step of merge sort by merging two
     * already sorted subarrays into a single sorted array.
     * 
     * Time Complexity: O(n) where n is the total number of elements
     * Space Complexity: O(1) as it uses the provided arrays
     * 
     * @param array The destination array where merged result will be stored
     * @param left  The left sorted subarray
     * @param right The right sorted subarray
     */
    private static void merge(int[] array, int[] left, int[] right) {
        int i = 0, j = 0, k = 0; // Pointers for left, right, and result arrays
        
        // Compare elements from both arrays and merge in sorted order
        while (i < left.length && j < right.length) {
            // Choose the smaller element and advance the corresponding pointer
            array[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
        }
        
        // Copy any remaining elements from the left array
        while (i < left.length) array[k++] = left[i++];
        
        // Copy any remaining elements from the right array
        while (j < right.length) array[k++] = right[j++];
    }

    /**
     * Quick Sort - An efficient, in-place, divide-and-conquer sorting algorithm
     * 
     * Time Complexity: 
     * - Best/Average case: O(n log n)
     * - Worst case: O(n^2) when pivot is always the smallest or largest element
     * Space Complexity: O(log n) due to recursion stack
     * Stability: Not stable (may change relative order of equal elements)
     * 
     * Algorithm Steps:
     * 1. Choose a pivot element (here: last element)
     * 2. Partition array so elements <= pivot are on left, > pivot on right
     * 3. Recursively apply quick sort to left and right partitions
     * 
     * @param array The integer array to be sorted
     * @param low   Starting index of the portion to sort
     * @param high  Ending index of the portion to sort
     */
    public static void quickSort(int[] array, int low, int high) {
        // Base case: if low >= high, the subarray has 0 or 1 element (already sorted)
        if (low < high) {
            // Partition the array and get the pivot's final position
            int pivotIndex = partition(array, low, high);
            
            // Recursively sort elements before the pivot
            quickSort(array, low, pivotIndex - 1);
            
            // Recursively sort elements after the pivot
            quickSort(array, pivotIndex + 1, high);
        }
    }

    /**
     * Partition - Helper method for Quick Sort using Lomuto partition scheme
     * 
     * This method rearranges the array such that:
     * - All elements <= pivot are moved to the left side
     * - All elements > pivot are moved to the right side
     * - The pivot is placed in its correct final position
     * 
     * Time Complexity: O(n) where n is the number of elements in the range
     * Space Complexity: O(1) - in-place partitioning
     * 
     * @param array The array to partition
     * @param low   Starting index of the range to partition
     * @param high  Ending index of the range to partition (pivot element)
     * @return      The final index position of the pivot element
     */
    private static int partition(int[] array, int low, int high) {
        int pivot = array[high]; // Choose the last element as pivot
        int i = low - 1; // Index of the smaller element (indicates right position of pivot)
        
        // Traverse through all elements except the pivot
        for (int j = low; j < high; j++) {
            // If current element is smaller than or equal to pivot
            if (array[j] <= pivot) {
                i++; // Increment index of smaller element
                
                // Swap elements to move smaller element to the left side
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        
        // Place pivot in its correct position by swapping with element at (i + 1)
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;
        
        return i + 1; // Return the partition index (pivot's final position)
    }

    /**
     * Main method for testing and benchmarking the sorting algorithms
     * 
     * This method:
     * 1. Tests both algorithms on datasets of different sizes
     * 2. Measures execution time in nanoseconds for performance comparison
     * 3. Uses random integers between 0-999 for realistic testing
     * 4. Ensures fair comparison by using identical datasets for both algorithms
     * 
     * Performance Notes:
     * - Merge Sort: Consistent O(n log n) performance regardless of data distribution
     * - Quick Sort: Generally faster than Merge Sort due to better cache locality,
     *   but performance can degrade to O(n^2) with poor pivot selection
     * 
     * @param args Command line arguments (not used)
     */
    public static void main(String[] args) {
        // Test with different dataset sizes to observe scaling behavior
        int[] sizes = {10, 50, 100};
        Random rand = new Random();
        
        System.out.println("=== Sorting Algorithms Performance Comparison ===\n");
        
        for (int size : sizes) {
            // Generate random dataset with integers between 0-999
            int[] original = rand.ints(size, 0, 1000).toArray();

            // Test Merge Sort - create a copy to ensure fair comparison
            int[] mergeInput = Arrays.copyOf(original, original.length);
            long startMerge = System.nanoTime();
            mergeSort(mergeInput);
            long endMerge = System.nanoTime();
            
            // Verify the array is sorted (optional validation)
            boolean mergeSorted = isSorted(mergeInput);

            // Test Quick Sort - use the same original dataset
            int[] quickInput = Arrays.copyOf(original, original.length);
            long startQuick = System.nanoTime();
            quickSort(quickInput, 0, quickInput.length - 1);
            long endQuick = System.nanoTime();
            
            // Verify the array is sorted (optional validation)
            boolean quickSorted = isSorted(quickInput);

            // Output detailed results with performance metrics
            System.out.printf("Dataset Size: %d elements\n", size);
            System.out.printf("Merge Sort: %d ns %s\n", 
                (endMerge - startMerge), 
                mergeSorted ? "[OK]" : "[ERROR: Not sorted!]");
            System.out.printf("Quick Sort: %d ns %s\n", 
                (endQuick - startQuick), 
                quickSorted ? "[OK]" : "[ERROR: Not sorted!]");
            
            // Calculate and display relative performance
            double ratio = (double)(endQuick - startQuick) / (endMerge - startMerge);
            System.out.printf("Quick/Merge Ratio: %.2fx %s\n\n", 
                ratio, 
                ratio < 1.0 ? "(Quick Sort faster)" : "(Merge Sort faster)");
        }
    }
    
    /**
     * Helper method to verify if an array is sorted in ascending order
     * 
     * This method provides validation that the sorting algorithms worked correctly
     * by checking if each element is less than or equal to the next element.
     * 
     * @param array The array to check
     * @return true if the array is sorted in ascending order, false otherwise
     */
    private static boolean isSorted(int[] array) {
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1]) {
                return false; // Found an element that breaks the sorted order
            }
        }
        return true; // All elements are in correct order
    }
}