merge_sort.c

#import <stdio.h>

void merge(int arr[], int leftIndex, int mid, int rightIndex){
	int leftSize = mid-leftIndex;
	int rightSize = rightIndex - mid + 1;
	int leftArr[leftSize];
	int rightArr[rightSize];

	// 1. fill left array
	for (int i = 0; i < leftSize; ++i)
	{
		leftArr[i] = arr[leftIndex+i];
	}
	// 2. fill right array
	for (int i = 0; i < rightSize; ++i)
	{
		rightArr[i] = arr[i+mid];
	}

	int i =0; int j = 0; int k = leftIndex;

	while(i<leftSize && j<rightSize){	
		printf("i=%d,j=%d,k=%d,left[i]=%d,right[j]=%d\n", i, j, k,leftArr[i],rightArr[j]);
		if (leftArr[i]<rightArr[j])
		{	
			arr[k] = leftArr[i];
			k++;
			i++;
		}else{
			arr[k] = rightArr[j];
			k++;
			j++;
		}
	}

	while(i<leftSize){
		arr[k] = leftArr[i];
		k++;
		i++;
	}
	while(j<rightSize){
		arr[k] = rightArr[j];
		k++;
		j++;
	}

	for (i = leftIndex; i <= rightIndex; ++i)
	{
		printf("%d\n", arr[i]);
	}
}

void mergeSort(int arr[], int leftIndex, int rightIndex){
	if (leftIndex==rightIndex)
	{
		return;
	}else{
		int mid = (leftIndex+rightIndex)/2;
		mergeSort(arr, leftIndex,mid);
		mergeSort(arr, mid+1, rightIndex);
		merge(arr,leftIndex,mid+1,rightIndex);
	}
}

int main(){
	// int arr[] = {2,4,6,8,1,3,5,7};
	int arr[] = {2,1,3,8,6,4,5,7};
	mergeSort(arr,0,7);
	// merge(arr, 0, 1, 1);
	// merge(arr, 2, 3, 3);
	// merge(arr, 4, 5, 5);
	// merge(arr, 6, 7, 7);

	// merge(arr, 0, 2, 3);
	// merge(arr, 4, 6, 7); 

	// merge(arr, 0, 4, 7); 
	return 0;
}