/*
	Implementation of the Merge Sort Algorithm
	Author: Marcos Castro - www.GeeksBR.com
*/

#include <stdio.h>
#include <stdlib.h> // malloc, free


// merge the vectors
void merge(int vec_left[], int vec_right[],
				int vec[], int size_vec_left, int size_vec_right, int size_vec)
{
	int i = 0, j = 0, k = 0;

	// makes the merge
	while(i < size_vec_left && j < size_vec_right)
	{
		if(vec_left[i] <= vec_right[j])
		{
			vec[k] = vec_left[i];
			i++;
		}
		else
		{
			vec[k] = vec_right[j];
			j++;
		}
		k++;
	}

	// fills with the rest of the elements
	while(i < size_vec_left)
	{
		vec[k] = vec_left[i];
		i++;
		k++;
	}

	while(j < size_vec_right)
	{
		vec[k] = vec_right[j];
		j++;
		k++;
	}
}


// merge sort algorithm
void merge_sort(int vec[], int size_vec)
{
	int *vec_left, *vec_right;
	int i, middle;

	if(size_vec < 2) // base condition
		return;

	middle = size_vec / 2; // gets the middle of the vector

	// creates two vectors
	vec_left = (int*)malloc(middle * sizeof(int));
	vec_right = (int*)malloc((size_vec - middle) * sizeof(int));

	// fills the vectors
	for(i = 0; i < middle; i++)
		vec_left[i] = vec[i];
	for(i = middle; i < size_vec; i++)
		vec_right[i - middle] = vec[i];

	// recursive calls
	merge_sort(vec_left, middle);
	merge_sort(vec_right, size_vec - middle);
	merge(vec_left, vec_right, vec, middle, size_vec - middle, size_vec);

	free(vec_right);
	free(vec_left);
}

int main()
{
	// the vector that will be sorted
	int vec[] = {25,40,55,20,44,35,38,99,10,65,50};
	int size_vec = sizeof(vec) / sizeof(int);

	// call merge sort
	merge_sort(vec, size_vec);

	// shows the sorted vector
	int i;
	for(i = 0; i < size_vec; i++)
		printf("%d ", vec[i]);

	return 0;
}