Algorithm Speed (2.00) :

Array Size (100) :

Radix Sort :

Author(s) : Herman Hollerith Date : 1887

Radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered.

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, exp1):
	n = len(arr)
	output = [0] * n
	count = [0] * 10
	for i in range(0, n):
		index = arr[i] // exp1
		count[index % 10] += 1
	for i in range(1, 10):
		count[i] += count[i - 1]
	i = n - 1
	while i >= 0:
		index = arr[i] // exp1
		output[count[index % 10] - 1] = arr[i]
		count[index % 10] -= 1
		i -= 1
	for i in range(0, len(arr)):
		arr[i] = output[i]

def radix_sort(arr):
	max1 = max(arr)
	exp = 1
	while max1 / exp >= 1:
		counting_sort(arr, exp)
		exp *= 10

function countingSort(arr, exp) {
	let n = arr.length;
	let output = new Array(n);
	let count = new Array(10).fill(0);
	for (let i = 0; i < n; i++) {
		count[Math.floor(arr[i] / exp) % 10]++;
	}
	for (let i = 1; i < 10; i++) {
		count[i] += count[i - 1];
	}
	for (let i = n - 1; i >= 0; i--) {
		output[count[Math.floor(arr[i] / exp) % 10] - 1] = arr[i];
		count[Math.floor(arr[i] / exp) % 10]--;
	}
	for (let i = 0; i < n; i++) {
		arr[i] = output[i];
	}
}

function radixSort(arr) {
	let max = Math.max(...arr);
	for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
		countingSort(arr, exp);
	}
}

public static void countingSort(int[] arr, int exp) {
	int n = arr.length;
	int[] output = new int[n];
	int[] count = new int[10];
	for (int i = 0; i < n; i++) {
		count[(arr[i] / exp) % 10]++;
	}
	for (int i = 1; i < 10; i++) {
		count[i] += count[i - 1];
	}
	for (int i = n - 1; i >= 0; i--) {
		output[count[(arr[i] / exp) % 10] - 1] = arr[i];
		count[(arr[i] / exp) % 10]--;
	}
	for (int i = 0; i < n; i++) {
		arr[i] = output[i];
	}
}

public static void radixSort(int[] arr) {
	int max = arr[0];
	for (int i = 1; i < arr.length; i++) {
		if (arr[i] > max) max = arr[i];
	}
	for (int exp = 1; max / exp > 0; exp *= 10) {
		countingSort(arr, exp);
	}
}

func countingSort(arr []int, exp int) {
	n := len(arr)
	output := make([]int, n)
	count := make([]int, 10)
	for i := 0; i < n; i++ {
		count[(arr[i]/exp)%10]++
	}
	for i := 1; i < 10; i++ {
		count[i] += count[i-1]
	}
	for i := n - 1; i >= 0; i-- {
		output[count[(arr[i]/exp)%10]-1] = arr[i]
		count[(arr[i]/exp)%10]--
	}
	for i := 0; i < n; i++ {
		arr[i] = output[i]
	}
}

func radixSort(arr []int) {
	max := arr[0]
	for _, v := range arr {
		if v > max {
			max = v
		}
	}
	for exp := 1; max/exp > 0; exp *= 10 {
		countingSort(arr, exp)
	}
}

void countingSort(int arr[], int n, int exp) {
	int *output = (int *)malloc(n * sizeof(int));
	int i, count[10] = {0};
	for (i = 0; i < n; i++) {
		count[(arr[i] / exp) % 10]++;
	}
	for (i = 1; i < 10; i++) {
		count[i] += count[i - 1];
	}
	for (i = n - 1; i >= 0; i--) {
		output[count[(arr[i] / exp) % 10] - 1] = arr[i];
		count[(arr[i] / exp) % 10]--;
	}
	for (i = 0; i < n; i++) {
		arr[i] = output[i];
	}
	free(output);
}

void radixSort(int arr[], int n) {
	int max = arr[0];
	for (int i = 1; i < n; i++) {
		if (arr[i] > max) max = arr[i];
	}
	for (int exp = 1; max / exp > 0; exp *= 10) {
		countingSort(arr, n, exp);
	}
}