#include <stdio.h>

void merge(int numbers[], int temp[], int left, int mid, int right);
void m_sort(int numbers[], int temp[], int left, int right);

int main()
{
	int Polje[11] = {3, 5, 15, 28, 30, 6, 10, 14, 22, 43, 50};
	int B[11];
	int i;

	// ispis nesortiranih brojeva
	printf("\nNesortirani brojevi: ");
	for (i = 0; i < 11; i++) 
		printf("%d ", Polje[i]);

	// poziv merge funkciji
	m_sort(Polje, B, 0, 10);

	// ispis sortiranih brojeva
	printf("\nSortirani brojevi: ");
	for (i = 0; i < 11; i++) 
		printf("%d ", Polje[i]);

	// zavrsili smo
	printf("\nKraj\n");
	return 0;
}

void ispis(int numbers[], int len, int left, int right)
{
	int i;

	printf("\nLeft: %d\tRight: %d\tA: ", left, right);
	for (i = 0; i < 11; i++) {
		printf("%d ", numbers[i]);
	}
}

void m_sort(int numbers[], int temp[], int left, int right)
{
	int mid;

	if (right > left) {
		mid = (right + left) / 2;
		m_sort(numbers, temp, left, mid);
		m_sort(numbers, temp, mid+1, right);
		ispis(numbers, right, left, right);
		merge(numbers, temp, left, mid+1, right);
		ispis(numbers, right, left, right);
	}
}

void merge(int numbers[], int temp[], int left, int mid, int right)
{
	int i, left_end, num_elements, tmp_pos;

	left_end = mid - 1;
	tmp_pos = left;
	num_elements = right - left + 1;

	while ((left <= left_end) && (mid <= right)) {
		if (numbers[left] <= numbers[mid]) {
			temp[tmp_pos] = numbers[left];
			tmp_pos = tmp_pos + 1;
			left = left +1;
		}
		else {
			temp[tmp_pos] = numbers[mid];
			tmp_pos = tmp_pos + 1;
			mid = mid + 1;
		}
	}

	while (left <= left_end) {
		temp[tmp_pos] = numbers[left];
		left = left + 1;
		tmp_pos = tmp_pos + 1;
	}

	while (mid <= right) {
		temp[tmp_pos] = numbers[mid];
		mid = mid + 1;
		tmp_pos = tmp_pos + 1;
	}

	for (i = 0; i <= num_elements; i++) {
		numbers[right] = temp[right];
		right = right - 1;
	}
}