Counting sort (cpp)

countingSort.cpp

// programming language: C++
// Running time complexity: O(n+K), where K is the maximum element in the array
// Space complexity: O(n+K)
#include <iostream>
using namespace std;
void countingSort(int* a, int n){

	// initial maximum value
	int mx=a[0];

	// new array to store sorted array
	int* output=new int[n];

	// stores occurence of each array element
	int* countArray=new int[mx+1];

	// finds the maximum element in the array a
	for(int i=0;i<n;i++){
		if(a[i]>mx){
			mx=a[i];
		}
	}

	/
	for(int i=0;i<mx+1;i++){
		countArray[i]=0;
	}
	for(int i=0;i<n;i++){
		countArray[a[i]]++;
	}

	for(int i=0;i<mx;i++){
		countArray[i+1]=countArray[i+1]+countArray[i];
	}

	for(int i=0;i<n;i++){
		int p=countArray[a[i]];
		countArray[a[i]]=p-1;
		output[p-1]=a[i];
	}
	for(int i=0;i<n;i++){
		cout << output[i] << endl;
	}

}
int main(){
	int a[]={9, 3, 1, 4, 6, 2, 1, 3, 8};
	countingSort(a, sizeof(a)/sizeof(a[0]));
	return 0;
}