int * merge(int *A, int a_size, int *B, int b_size)
{
	int ai, bi, ci, i;
	int * C;
	int c_size = a_size + b_size;
	ai = bi = ci = 0;
	C = (int*)malloc(c_size*sizeof(int));
	while ((ai < a_size) && (bi < b_size))
	{
		if (A[ai] < B[bi])
		{
			C[ci] = A[ai];
			ai++;
			ci++;
		}
		else
		{
			C[ci] = B[bi];
			bi++;
			ci++;
		}
	}
	if (ai >= a_size)
		for (i = ci; i < c_size; i++, bi++)
			C[i] = B[bi];
	else if (bi >= b_size)
		for (i = ci; i < c_size; i++, ai++)
			C[i] = A[ai];
	for (i = 0; i < a_size; i++)
		A[i] = C[i];
	for (i = 0; i < b_size; i++)
		B[i] = C[a_size + i];
	return C;
}

void merge_sort(int *A, int min, int max)
{
	int *C;
	int mid = (min + max) / 2;
	int left = mid - min + 1;
	int right = max - mid;
	if (max != min)
	{
		merge_sort(A, min, mid);
		merge_sort(A, mid + 1, max);
		C = merge(A + min, left, A + mid + 1, right);
	}
}