#include <stdio.h>
	#include <stdlib.h>

	// Function Prototypes
	void mergeSortWrapper(int *arr, int len);
	void mergeSort(int *arr, int left, int right);
	void merge(int *arr, int left, int mid, int right);
	void printArr(int *arr, int len);

	// Calls recursive mergeSort with appropriate arguments
	void mergeSortWrapper(int *arr, int len) { mergeSort(arr, 0, len - 1); }

	// Recursively splits workload of sorting array by half every iteration
	// Once each array is recursively parsed so far that the final recursive
	// call only references sub-array of size 1
	// Function will recursively backtrack to merge each previous split
	void mergeSort(int *arr, int left, int right) {
		if (left >= right)
			return;
		int mid = (left + right) / 2;
		mergeSort(arr, left, mid);      // T(n/2)
		mergeSort(arr, mid + 1, right); // T(n/2)
		merge(arr, left, mid, right);   // O(n)

		// Recurrence Relation: T(n/2) + T(n/2) + O(n) = 2T(n/2) + O(n)
		// Runtime - O(nlogn)
	}

	// Creates temporary array to store the sorted version of array
	// Utilizes parallel tracking to put elements into temp array in sorted order
	// Then sets values at corresponding indexes in original array to sorted values
	void merge(int *arr, int left, int mid, int right) {
		int L = left;
		int R = mid + 1;
		int *temp = malloc((right - left + 1) * sizeof(int));
		int k = 0;
		while (L <= mid && R <= right) {
			// Pushing left index if arr[L] = arr[R] keeps this sorting algorithm stable
			if (arr[L] <= arr[R])
				temp[k++] = arr[L++];
			else
				temp[k++] = arr[R++];
		}
		// Once one index tracker goes out of bounds, push remaining elements
		// from other half of the array
		while (L <= mid)
			temp[k++] = arr[L++];

		while (R <= right)
			temp[k++] = arr[R++];

		// Copy sorted values into original array
		for (int i = left; i <= right; i++) {
			arr[i] = temp[i - left];
		}

		free(temp);
	}

	// Print integer array to screen
	void printArr(int *arr, int len) {
		for (int i = 0; i < len; i++)
			printf("%d ", arr[i]);
		printf("\n\n");
	}

	int main(void) {
		int len = 20;
		int *arr = malloc(len * sizeof(int));
		for (int i = 0; i < len; i++) {
			arr[i] = rand() % 100;
		}
		printf("Printing Array...\n\n");
		printArr(arr, len);
		printf("Applying Merge Sort...\n\n");
		mergeSortWrapper(arr, len);
		printf("Printing Sorted Array...\n\n");
		printArr(arr, len);
		free(arr);
		return 0;
	}