/*
 ============================================================================
 Name        : eal05heapsort.c
 Author      :
 Version     :
 Copyright   : Your copyright notice
 Description : Hello World in C, Ansi-style
 ============================================================================
 */

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

void swap(int* a, int* b)
{
	int t = *a;
	*a = *b;
	*b = t;
}

void versenke(int* arr, int i, int size)
{
	while( i<=((size/2)-1) )
	{
		int kindIndex = ((i+1)* 2)-1;// berechne index kind

		//welches kind groeßer
		if(kindIndex < size-1)
		{
			if(arr[kindIndex] < arr[kindIndex+1])
			{
				kindIndex++;
			}
		}
		//teste ob element sinken muss
		if(arr[i] < arr[kindIndex])
		{
			swap(arr+i, arr+kindIndex);
			i=kindIndex; // wiederhole mit neuer pos
		}
		else
		{
			break;
		}
	}
}


void heapsort(int* arr, int size)
{
	//init maxheap!
	int i;
	for(i=size/2-1; i>=0; i--)
	{
		versenke(arr, i, size);
	}

	//hier wird sortiert!!!

	for(i=size-1; i>0; i--)
	{
		swap(arr+i, arr);
		versenke(arr, 0, i);
	}


}



void merge(int* a, int l, int m, int r)
{
	int *b=malloc(sizeof(int) * r);
	int i=0;
	int j,k;

	for(i=l; i<r; i++)
	{
		b[i]=a[i];
	}

	i=l;
	j=m+1;
	k=l;
	while(i<=m && j<r)
	{
		if(b[i]<=b[j])
		{
			a[k]=b[i];
			k++;
			i++;
		}
		else
		{
			a[k]=b[j];
			k++;
			j++;
		}
	}

	while(i<=m)
	{
		a[k]=b[i];
		k++;
		i++;
	}

	while(j<r)
	{
		a[k]=b[j];
		k++;
		j++;
	}
	free(b);
}


void mergesort(int*arr, int l, int r)
{
	if(l<r)
	{
		int m = (l+r)/2;
		mergesort(arr, l, m);
		mergesort(arr, m+1, r);
		merge(arr, l, m, r);
	}
}



int main(void)
{
	int size=9;
	int i;
	int *test=malloc(sizeof(int)*size);
	for(i=0; i<size; i++)
		test[i]=42-i;

	mergesort(test, 0, size);


	for(i=0; i<size; i++)
		printf("%i,", test[i]);
	printf("\n");

	free(test);
	return 1;
}