package sorts;

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

/**
 * A generic sort algorithm that implements the SortAlgorithm interface.
 * Other algorithms extend this class to implement their own sorting logic.
 * !!!!!!!!!!! DO NOT MODIFY THIS FILE !!!!!!!!!
 */
public abstract class GenericSortAlgorithm extends RecursiveAction implements SortAlgorithm {

    protected static ForkJoinPool pool = new ForkJoinPool();
    
    // For very small arrays, use insertion sort (to reduce overhead)
    private static final int INSERTION_THRESHOLD = 10;
    
    protected int[] array;
    protected int left;
    protected int right;
    
	public GenericSortAlgorithm() {
	}
	
	public GenericSortAlgorithm(int[] array, int left, int right) {
		this.array = array;
		this.left = left;
		this.right = right;
	}
	@Override
    // Public method to initiate the sort
    public void sort(int[] array) {
    	this.array = array;
    	this.left=0;
		this.right = array.length - 1;
		pool.invoke(this);
		//compute();
    }
	
	protected void insertionSort(int[] arr, int low, int high) {
        for (int i = low + 1; i <= high; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= low && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
    
    protected void quickSort(int[] arr, int low, int high) {
        // For very small arrays, use insertion sort
        if (high - low < INSERTION_THRESHOLD) {
            insertionSort(arr, low, high);
        } else if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

	protected int partition(int[] arr, int low, int high) {
		int pivot = arr[high];
		int i = low - 1;
		for (int j = low; j < high; j++) {
			if (arr[j] <= pivot) {
				i++;
				swap(arr, i, j);
			}
		}
		swap(arr, i + 1, high);
		return i + 1;
	}
	
	protected void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}