//*******************Merge Sort**************************

void merge(int*a, int start, int middle, int end, int*b) {
	int i;
	int j = start;
	int k = middle + 1;
	for (i = start; j <= middle && k <= end; i++) {
		if (a[j] > a[k]) {
			b[i] = a[j];
			j++;
		} else {
			b[i] = a[k];
			k++;
		}
	}
	while (j <= middle)
		b[i++] = a[j++];

	while (k <= end)
		b[i++] = a[k++];

	for (i = start; i <= end; i++)
		a[i] = b[i];
}

//*******************Merge Sort**************************

void mergeSortR(int* a, int start, int end, int* b) {
	int		middle;
	if (start >= end) return;

	middle = start + (end - start) / 2;
	mergeSortR(a, start, middle, b);
	mergeSortR(a, middle + 1, end, b);
	merge(a, start, middle, end, b);
}

long mergeSort(int* a, int n) {
	int* b = malloc(sizeof(int) * n);
	int i;
	for (i = 0; i < n; i++) {
		b[i] = a[i];
	}
	mergeSortR(a, 0, n - 1, b);
	return 0;
}
//*******************Bucket Sort**************************