package edu.cmich.cps181;

import java.util.ArrayList;

public class MergeSort {
	public static <T> void merge(ArrayList<T> randomInputs, int i, int j, int k) {
		int mergedSize = k - i + 1; // Size of merged partition
		int mergedNumbers[] = new int[mergedSize]; // Temporary array for merged numbers
		int mergePos = 0; // Position to insert merged number
		int leftPos = 0; // Position of elements in left partition
		int rightPos = 0; // Position of elements in right partition

		leftPos = i; // Initialize left partition position
		rightPos = j + 1; // Initialize right partition position

		// Add smallest element from left or right partition to merged numbers
		while (leftPos <= j && rightPos <= k) {
			if ((int) randomInputs.get(leftPos) < (int) randomInputs.get(rightPos)) {
				mergedNumbers[mergePos] = (int) randomInputs.get(leftPos);
				++leftPos;
			} else {
				mergedNumbers[mergePos] = (int) randomInputs.get(rightPos);
				++rightPos;
			}
			++mergePos;
		}

		// If left partition is not empty, add remaining elements to merged numbers
		while (leftPos <= j) {
			mergedNumbers[mergePos] = (int) randomInputs.get(leftPos);
			++leftPos;
			++mergePos;
		}

		// If right partition is not empty, add remaining elements to merged numbers
		while (rightPos <= k) {
			mergedNumbers[mergePos] = (int) randomInputs.get(rightPos);
			++rightPos;
			++mergePos;
		}

		// Copy merge number back to numbers
		for (mergePos = 0; mergePos < mergedSize; ++mergePos) {
			randomInputs.set(i + mergePos, mergedNumbers[mergePos]);
		}
	}

	public static <T> void mergesort(ArrayList<T> randomInputs, int i, int k) {//i = 0 and k = length
		int j = 0;

		if (i < k) {
			j = (i + k) / 2; // Find the midpoint in the partition

			// Recursively sort left and right partitions
			mergesort(randomInputs, i, j);
			mergesort(randomInputs, j + 1, k);

			// Merge left and right partition in sorted order
			merge(randomInputs, i, j, k);
		}
	}

}