Algorithm Speed (2.00) :

Array Size (100) :

Counting Sort :

Author(s) : Harold H. Seward Date : 1954

Counting sort is an integer sorting algorithm that operates by counting the number of objects that possess distinct key values, and applying prefix sum on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items.

Time Complexity	O(n + k)
Best Case	O(n + k)
Worst Case	O(n + k)
Space Complexity	O(n + k)
Stable	Yes

def counting_sort(arr):
	if not arr:
		return []
	max_val = max(arr)
	min_val = min(arr)
	range_of_elements = max_val - min_val + 1
	count = [0] * range_of_elements
	output = [0] * len(arr)
	for i in range(len(arr)):
		count[arr[i] - min_val] += 1
	for i in range(1, len(count)):
		count[i] += count[i - 1]
	for i in range(len(arr) - 1, -1, -1):
		output[count[arr[i] - min_val] - 1] = arr[i]
		count[arr[i] - min_val] -= 1
	for i in range(len(arr)):
		arr[i] = output[i]
	return arr

function countingSort(arr) {
	if (arr.length === 0) return arr;
	let min = Math.min(...arr);
	let max = Math.max(...arr);
	let count = new Array(max - min + 1).fill(0);
	let output = new Array(arr.length);
	for (let i = 0; i < arr.length; i++) {
		count[arr[i] - min]++;
	}
	for (let i = 1; i < count.length; i++) {
		count[i] += count[i - 1];
	}
	for (let i = arr.length - 1; i >= 0; i--) {
		output[count[arr[i] - min] - 1] = arr[i];
		count[arr[i] - min]--;
	}
	for (let i = 0; i < arr.length; i++) {
		arr[i] = output[i];
	}
	return arr;
}

public static void countingSort(int[] arr) {
	if (arr.length == 0) return;
	int max = arr[0];
	int min = arr[0];
	for (int i = 1; i < arr.length; i++) {
		if (arr[i] > max) max = arr[i];
		if (arr[i] < min) min = arr[i];
	}
	int[] count = new int[max - min + 1];
	int[] output = new int[arr.length];
	for (int i = 0; i < arr.length; i++) {
		count[arr[i] - min]++;
	}
	for (int i = 1; i < count.length; i++) {
		count[i] += count[i - 1];
	}
	for (int i = arr.length - 1; i >= 0; i--) {
		output[count[arr[i] - min] - 1] = arr[i];
		count[arr[i] - min]--;
	}
	for (int i = 0; i < arr.length; i++) {
		arr[i] = output[i];
	}
}

func countingSort(arr []int) {
	if len(arr) == 0 {
		return
	}
	max := arr[0]
	min := arr[0]
	for _, v := range arr {
		if v > max {
			max = v
		}
		if v < min {
			min = v
		}
	}
	count := make([]int, max-min+1)
	output := make([]int, len(arr))
	for _, v := range arr {
		count[v-min]++
	}
	for i := 1; i < len(count); i++ {
		count[i] += count[i-1]
	}
	for i := len(arr) - 1; i >= 0; i-- {
		output[count[arr[i]-min]-1] = arr[i]
		count[arr[i]-min]--
	}
	for i := 0; i < len(arr); i++ {
		arr[i] = output[i]
	}
}

void countingSort(int arr[], int n) {
	if (n == 0) return;
	int max = arr[0];
	int min = arr[0];
	for (int i = 1; i < n; i++) {
		if (arr[i] > max) max = arr[i];
		if (arr[i] < min) min = arr[i];
	}
	int range = max - min + 1;
	int *count = (int *)calloc(range, sizeof(int));
	int *output = (int *)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++) {
		count[arr[i] - min]++;
	}
	for (int i = 1; i < range; i++) {
		count[i] += count[i - 1];
	}
	for (int i = n - 1; i >= 0; i--) {
		output[count[arr[i] - min] - 1] = arr[i];
		count[arr[i] - min]--;
	}
	for (int i = 0; i < n; i++) {
		arr[i] = output[i];
	}
	free(count);
	free(output);
}