#include <stdio.h> 
#include <stdlib.h> 
#include <sys/times.h> 
#include <sys/resource.h>

#define DIM 8000 
main() 
{ 
      struct tms buffer; 
      int feld[DIM]; 
      int feld_kopie[DIM]; 
      int feld_kopie2[DIM]; 
      int feld_kopie3[DIM]; 

      int i; 
      for (i=0;i<DIM;i++) 
	      { 
	      //feld[i] = feld_kopie[i] = feld_kopie2[i]=  feld_kopier3[i]= rand(); 
	      feld[i] = feld_kopie[i] = feld_kopie2[i]= feld_kopie3[i]= DIM-i;
	      } 
      times(&buffer); 
      printf("Zeit vor dem Sortieren: %d\n",buffer.tms_utime); 
      my_qsort_000000(feld, DIM ); 
      times(&buffer); 
      printf("Zeit vor dem UNIX Sortieren: %d\n",buffer.tms_utime); 
      my_qsort_000000(feld_kopie, DIM ); 
      times(&buffer); 
      printf("Zeit nach dem UNIX Sortieren: %d\n",buffer.tms_utime); 

      if (memcmp(feld,feld_kopie, DIM * sizeof(int) ) != 0) 
	      printf("Wir haben Probleme, die beiden Felder sind nach dem Sortieren verschieden\n"); 

      my_qsort_mies_000000(feld_kopie3, DIM ); 
      times(&buffer); 
      printf("Zeit nach dem miesen Sortieren: %d\n",buffer.tms_utime); 
      if (memcmp(feld,feld_kopie3, DIM * sizeof(int) ) != 0) 
	      printf("Wir haben Probleme, die beiden Felder sind nach dem dritten(miesen) Sortieren verschieden\n"); 

      my_qsort_ganzmies_000000(feld_kopie2, DIM ); 
      times(&buffer); 
      printf("Zeit nach dem ganz miesen Sortieren: %d\n",buffer.tms_utime); 
      if (memcmp(feld,feld_kopie2, DIM * sizeof(int) ) != 0) 
	      printf("Wir haben Probleme, die beiden Felder sind nach dem zweiten(ganz miesen) Sortieren verschieden\n"); 
} 

my_comp(int *a, int *b) 
{ 
      return *a - *b; 
} 

my_qsort_000000(int *feld, int feld_laenge) 
{ 
      qsort(feld,feld_laenge, sizeof(int), my_comp); 
} 

my_qsort_ganzmies_000000(int *feld, int feld_laenge)
{
	int i,i_links,i_rechts,i_mitte,vergleichswert;
	int feld_laenge_links=0,feld_laenge_rechts=0,feld_laenge_mitte=0;
	int *feld_links,*feld_rechts,*feld_mitte;
	if (feld_laenge <= 1) return;
	vergleichswert=feld[0];
	for (i = 0;i<feld_laenge;i++)
		if (feld[i]<vergleichswert) feld_laenge_links++;
		else if  (feld[i] == vergleichswert) feld_laenge_mitte++;
	feld_laenge_rechts=feld_laenge-feld_laenge_links-feld_laenge_mitte;
	feld_links = (int *)calloc(sizeof(int),feld_laenge_links);
	feld_rechts = (int *)calloc(sizeof(int),feld_laenge_rechts);
	feld_mitte = (int *)calloc(sizeof(int),feld_laenge_mitte);
	if (feld_links == NULL) exit(1);
	if (feld_rechts == NULL) exit(1);
	if (feld_mitte == NULL) exit(1);
	for (i = 0,i_links=0,i_rechts=0,i_mitte=0;i<feld_laenge;i++)
		if (feld[i]<vergleichswert) feld_links[i_links++]=feld[i];
		else if  (feld[i] == vergleichswert)  feld_mitte[i_mitte++]=feld[i];
		else  feld_rechts[i_rechts++]=feld[i];
	my_qsort_ganzmies_000000(feld_links,feld_laenge_links);
	for (i = 0;i<feld_laenge_links;i++)  
		feld[i]=feld_links[i];
	free(feld_links);	
	for (i = 0;i<feld_laenge_mitte;i++)  
		feld[i+feld_laenge_links]=feld_mitte[i];
	free(feld_mitte);	
	my_qsort_ganzmies_000000(feld_rechts,feld_laenge_rechts);
	for (i = 0;i<feld_laenge_rechts;i++)  
		feld[i+feld_laenge_links+feld_laenge_mitte]=feld_rechts[i];
	free(feld_rechts);	
}
my_qsort_mies_000000(int *feld, int feld_laenge)
{
	int i,i_links,i_rechts,i_mitte,vergleichswert;
	int feld_laenge_links=0,feld_laenge_rechts=0,feld_laenge_mitte=0;
	int *feld_links,*feld_rechts,*feld_mitte;
	if (feld_laenge <= 1) return;
	vergleichswert=feld[0];
	for (i = 0;i<feld_laenge;i++)
		if (feld[i]<vergleichswert) feld_laenge_links++;
		else if  (feld[i] == vergleichswert) feld_laenge_mitte++;
	feld_laenge_rechts=feld_laenge-feld_laenge_links-feld_laenge_mitte;

	if (feld_laenge_links < feld_laenge_rechts){

		feld_links = (int *)calloc(sizeof(int),feld_laenge_links); 
		if (feld_links == NULL) exit(1);
		for (i = 0,i_links=0,i_rechts=0,i_mitte=0;i<feld_laenge;i++)
			if (feld[i]<vergleichswert) feld_links[i_links++]=feld[i]; 

		my_qsort_mies_000000(feld_links,feld_laenge_links);
		feld_mitte = (int *)calloc(sizeof(int),feld_laenge_mitte);    
		if (feld_mitte == NULL) exit(1);
		feld_rechts=feld+feld_laenge_links+feld_laenge_mitte;
		for (i = feld_laenge-1,i_rechts=feld_laenge_rechts-1;i>=0;i--)
			if  (feld[i] == vergleichswert)  feld_mitte[i_mitte++]=feld[i];
			else  if (feld[i] > vergleichswert) feld_rechts[i_rechts--]=feld[i];
		for (i = 0;i<feld_laenge_links;i++)  
			feld[i]=feld_links[i];
		free(feld_links);	
		for (i = 0;i<feld_laenge_mitte;i++)  
			feld[i+feld_laenge_links]=feld_mitte[i];
		free(feld_mitte);	
		my_qsort_mies_000000(feld_rechts,feld_laenge_rechts);
	}
	else	{
		feld_rechts = (int *)calloc(sizeof(int),feld_laenge_rechts);
		if (feld_rechts == NULL) exit(1);
		for (i = 0,i_links=0,i_rechts=0,i_mitte=0;i<feld_laenge;i++)
			if (feld[i]>vergleichswert) feld_rechts[i_rechts++]=feld[i];
		my_qsort_mies_000000(feld_rechts,feld_laenge_rechts);

		feld_mitte = (int *)calloc(sizeof(int),feld_laenge_mitte);
		if (feld_mitte == NULL) exit(1);
		feld_links=feld;
		for (i = 0,i_links=0,i_rechts=0,i_mitte=0;i<feld_laenge;i++)
			if (feld[i]<vergleichswert) feld_links[i_links++]=feld[i];
			else if  (feld[i] == vergleichswert)  feld_mitte[i_mitte++]=feld[i];   

		for (i = 0;i<feld_laenge_rechts;i++)  
			feld[i+feld_laenge_links+feld_laenge_mitte]=feld_rechts[i];
		free(feld_rechts);	
		
		for (i = 0;i<feld_laenge_mitte;i++)  
			feld[i+feld_laenge_links]=feld_mitte[i];
		free(feld_mitte);	

		my_qsort_mies_000000(feld_links,feld_laenge_links);
	}
}