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

void insertionSort(int size, int array[]){
	//Einige Variablen deklarieren
	int key;
	int i;
	int j;
	
	//Algorithmus starten, Pseudocode aus der Vorlesung in c ausformuliert
	for(j = 1; j<size; j++){
		//tempvariable mit dem aktuellen wert belegen
		key = array[j];
		i = j-1;
		//solange wert groesser ist, verschiebe
		while(i>=0 && array[i]>key){
			array[i+1] = array[i];
			i = i-1;
		}
		//letztendlich wert zurueckschreiben
		array[i+1] = key;
	}
	
	}
//Merget die Arrays A und B mit den Groessen m und n nach C
void merge(int m, int n, int A[], int B[], int C[]) {
      int i, j, k;
      i = 0;
      j = 0;
      k = 0;
      int p;
      //Solange beide Zaehler sich in den Grenzen der Arrays bewegen...
      while (i < m && j < n) {
      		//Wenn linke Haelfte kleiner als rechte Haelfte
            if (A[i] <= B[j]) {
            	//Schreibe linke Haelfte ins Zielarray
                  C[k] = A[i];
                  i++;
            } else {
            	//Sonst schreibe rechte Haelfte
                  C[k] = B[j];
                  j++;
            }
            k++;
      }
      //Behandle Sonderfaelle, falls ein Teilarray leer ist
      if (i < m) {
      		//Behandle nur linken Teilarray
            for (p = i; p < m; p++) {
                  C[k] = A[p];
                  k++;
            }
      } else {
      		//Behandle nur rechten Teilarray
            for (p = j; p < n; p++) {
                  C[k] = B[p];
                  k++;
            }
      }
}

 void mergeSort(int liste[], int groesse){
 	//Solang Abbruchbedingung der Rekursion noch nicht erreicht ist...
     if(groesse > 1){
 		//Linke Haelfte definieren
         int haelfte1[groesse/2];
         //Rechte Haelfte definieren
         int haelfte2[(groesse + 1)/2];
         int i;
         //Linke Haelfte fuellen
         for(i = 0; i < groesse/2; ++i)
             haelfte1[i] = liste[i];
         //Rechte Haelfte fuellen
         for(i = groesse/2; i < groesse; ++i)
             haelfte2[i - groesse/2] = liste[i];
 			//MergeSort ueber die linke und rechte Haelfte laufen lassen
         mergeSort(haelfte1,groesse/2);
         mergeSort(haelfte2,(groesse + 1)/2);
         //Die gesplitteten Arrays mergen
         merge(groesse/2, (groesse+1)/2, haelfte1, haelfte2, liste);
     }
 }


int main( int argc, const char* argv[] ){
	//Globale Variablen deklarieren
	int size;
	int isRand = 1;
	int isAuf = 1;
	int isAb = 1;
	int isMerge = 1;
	int isInsertion = 1;
	int *array;
	int i;
	double secs; 
	clock_t tStart, tEnd; 

	
	//Randomizer starten
	srand(time(NULL));
	
	//Wenn genügend Argumente am Start sind, lies dir Groesse aus.
	if(argc > 1){
		size = atoi(argv[1]);
	}else{
		//Sonst beschwer dich
		printf("Zu wenig argumente.\n");
		return 1;
	}
	
	//Wenn die Groesse irreal ist, beschwer dich
	if (size < 1){
		printf("Die angegebene Groesse kann nicht verarbeitet werden.\n");
		return 1;
	}
	
	//Allokiere das Array
	array = malloc(size * sizeof(int));
	if(array == NULL){
		printf("Nicht genug Speicher vorhanden\n");
		return 1;
	}
	
	//Ausgehend von der Menge der uebergebenen Argumente die Vorgehensweise ermitteln
	if(argc == 2){
		//Default merch und rand
		isRand = 0;
		isMerge = 0;
	}else if(argc == 3){
		//Sortiermethode abfragen, Fuellmethode default auf rand setzen
		isMerge = strcmp(argv[2], "merge");
		isInsertion = strcmp(argv[2], "insert");
		isRand = 0;
	}else if (argc == 4){
		//fuell- und sortiermethode abfragen
		isRand = strcmp(argv[3], "rand");
		isAuf = strcmp(argv[3], "auf");
		isAb = strcmp(argv[3], "ab");
		isMerge = strcmp(argv[2], "merge");
		isInsertion = strcmp(argv[2], "insert");
	}
	
	//Array fuellen
	if(!isRand){
		//Beginn Array randomized fuellen
		for(i = 0; i<size; i++){
			array[i] = 1 + ( rand() % size ) ;
		}
		//Ende Array randomized fuellen
	}else if (!isAuf){
		//Beginn Array aufsteigend fuellen
		for(i = 0; i<size; i++){
			array[i] = i;
		}
		//Ende Array aufsteigend fuellen
	}else if (!isAb){
		//Beginn Array absteigend fuellen
		for(i = 0; i<size; i++){
			array[i] = size-i;
		}
		//Ende Array absteigend fuellen
	}else{
		printf("Methode nicht bekannt.\n");
		free(array);
		return 1;
	}

	
	tStart = clock();
	if(!isMerge && isInsertion){
		printf("Sortiere mit Mergesort\n");
		mergeSort(array, size);
	}else if(!isInsertion && isMerge){
		printf("Sortiere mit Insertionsort\n");
		insertionSort(size, array);
	}
	tEnd = clock();
	secs = (double)(tEnd - tStart) / CLOCKS_PER_SEC; 

	if(size <= 1000){
		for(i = 0; i<size; i++){
			printf("Element %u: %u \n", i, array[i]);
		}
	}
	
	//Array auf korrekte Sortierung pruefen
	for(i = 0; i<(size-1); i++){
		if(array[i]>array[i+1]){
			printf("Array ist NICHT sortiert. ");
			break;
		}
	}
	
	//Ergebnis der Zeitmessung ausgeben.
	printf("Das hat jetzt %f Sekunden gedauert.\n", secs);
	
	//Toete das Array und beende das Programm erfolgreich.
	free(array);
	return 0;
}