//merge sort
// by kaan ata

#include <stdlib.h>
#include <stdio.h>
#include <time.h>       
 
#define MAX 10
void Yaz_dizi(const int *dizi, int boyut); 
void Doldur(int *dizi, int boyut);
void Degis(int *dizi, int a, int src);
void Birles(int *dizi, int sol, int sag, int nokta);
void MergeSort(int *dizi, int sol, int sag, int nokta);
 
int main(void)
{
        int dizi[MAX];
        
		Doldur(dizi, MAX);            
        
		printf("Dizi:\t"); 
		
		Yaz_dizi(dizi, MAX);
        
		MergeSort(dizi, 0, MAX - 1, MAX / 2);
        
		printf("Merge Sort:\t");
		
		Yaz_dizi(dizi, MAX);
        
		return 0;
}

void Yaz_dizi(const int *dizi, int boyut)
{
        int i;
        for(i = 0; i < boyut; i ++) printf("%d ",dizi[i]);
        printf("\n");
}
 
void Doldur(int *dizi, int boyut)  
{
        int i;         
		srand(time(NULL));         
        for(i = 0; i < boyut; i ++) dizi[i] = rand() % 100; 

		
}
 
void Degis(int *dizi, int a, int src)
{
        int i = src;
        int tut = dizi[src];     
        for(; i > a; i --) dizi[i] = dizi[i - 1]; 
        dizi[a] = tut;                        
}
 
void Birles(int *dizi, int sol, int sag, int nokta)
{
        int i = sol, j = nokta + 1;
        while (j != sag + 1)                 
        {
                if(dizi[j] <= dizi[i])       
                Degis(dizi, i ++ , j ++);    
                else i ++;                   
        }
}
 
void MergeSort(int *dizi, int sol, int sag, int nokta)
{
        if(sol == sag) return;
        else
        {
                MergeSort(dizi, sol, nokta, (sol + nokta) / 2);  
				MergeSort(dizi, nokta + 1, sag, (nokta + sag + 1) / 2);
        }
        Birles(dizi, sol, sag, nokta);    
}