mergeSort.cpp

#include <iostream>
void printArray(int *A, int n){
	for (int i=0;i<n;i++){ std::cout<<A[i]<<' ';}
	std::cout<<'\n';
}
void merge(int *A, int *left, int *right, int n1, int n2){
	int i=0,j=0,k=0;
	while (i<n1 && j<n2){
		if (left[i]<right[j]){A[k]=left[i];i++;k++;}
		else {A[k]=right[j];j++;k++;}
	}
	while (i<n1){A[k]=left[i];i++;k++;}
	while (j<n2){A[k]=right[j];j++;k++;}
}
void mergeSort(int *A, int n){
	if (n==1) return;
	int *left = new int[n/2], *right=new int[n-n/2], i=0;
	while (i<n/2){left[i]=A[i];i++;}
	while (i<n){right[i-n/2]=A[i];i++;}
	mergeSort(left,n/2);
	mergeSort(right,n-n/2);
	merge(A,left,right,n/2,n-n/2);
}
int main(){
	int A[] = {3,2,1,6,8,2,1,3,9};
	int n = sizeof(A)/sizeof(int);
	printArray(A,n);
	mergeSort(A,n);
	printArray(A,n);
	return 0;
}