#include <pthread.h>
#include <stdio.h>

int* data;
int* buf;

int split(int st, int ed){
int i, stp, edp;
	stp=st; edp=ed;
	for(i=st; i<=ed; i++){
		if(data[i]<data[st]){
			buf[stp]=data[i];
			stp++;
		}else{
			buf[edp]=data[i];
			edp--;
		}
	}
	for(i=st; i<=ed; i++){
		data[i]=buf[i];
	}
	return edp;
}

void* qsort(void* x){
int st, ed;
	sscanf(x, "%d:%d", &st, &ed);
	// printf("%d - %d\n", st, ed);

	if(st<ed){
	pthread_t thre1, thre2;
	int cr;
	char range1[10], range2[10];
		cr=split(st, ed);
		sprintf(range1, "%d:%d", st, cr);
		pthread_create(&thre1, NULL, qsort, range1);
		sprintf(range2, "%d:%d", cr+1, ed);
		pthread_create(&thre2, NULL, qsort, range2);
		pthread_join(thre1, NULL);
		pthread_join(thre2, NULL);
	}
}

main(int argc, char* argv[]){
pthread_t thre;
char range[10];
int i;

	if(argc<2) exit(2);
	data=(int*)calloc(sizeof(int), argc-1);
	buf=(int*)calloc(sizeof(int), argc-1);
	if(data==NULL || buf==NULL) exit(1);
	for(i=0; i<argc-1; i++){
		data[i]=atoi(argv[i+1]);
	}
	sprintf(range, "%d:%d", 0, argc-2);

	pthread_create(&thre, NULL, qsort, range);
	pthread_join(thre, NULL);

	for(i=0; i<argc-1; i++){
		printf("%d ", data[i]);
	}
	printf("\n");
}