Mergesort.c

void mergeS(int *a, int n, int *temp){
	//base case
	if (n <= 1) {
		return;
	}
	//recursion stuff
	mergeS(a, n / 2, temp);
	mergeS(a + n/2, n - n / 2, temp);

	int i = 0, j = n / 2, k = 0;
	while (i < n / 2 && j < n) {
		//basically compare the leftmost element to the middle of the list
		//then if the smallest element is the leftmost element, put it as the first element of a temp list
		//and vice versa
		if (a[i] <= a[j]) {
			temp[k] = a[i];
			k++; i++;
		}
		else {
			temp[k] = a[j];
			k++; j++;
		}
	}
	//Copy the rest (since the loop earlier terminates before all elements are copied
	while (i < n / 2) {
		temp[k] = a[i];
		k++; i++;
	}
	while (j < n) {
		temp[k] = a[j];
		k++; j++;
	}

	//merge to the main list
	for (i = 0; i < n; i++) {
		a[i] = temp[i];
	}
}