Algorithm Speed (2.00) :

Array Size (100) :

Radix Sort :

Author(s) : Unknown Date : Ancient

Radix sort is a non-comparison-based sorting technique that exploits the positional nature of numbers (e.g., digits in base-10). It works by repeatedly sorting the input data on each digit position (least significant digit first) using a counting sort or similar stable sorting algorithm. After a pass on a particular digit position, the elements are placed in stable sub-lists based on their digit values. These sub-lists are then concatenated to form a partially sorted list. The process is repeated for higher-order digit positions until the entire array is sorted. Radix sort has a time complexity of O(n * k/d), where k is the number of digits and d is the number of elements. This makes it efficient for data with a fixed number of digits or where values fall within a specific range.

Time Complexity	O(n * k/d)
Best Case	O(n)
Worst Case	O(n * k/d)
Space Complexity	O(n + 2ᵈ)
Stable	Yes

def radix_sort(arr):
	max_value = max(arr)
	exp = 1
	while max_value // exp > 0:
		buckets = [[] for _ in range(10)]
		for i in arr:
			index = (i // exp) % 10
			buckets[index].append(i)
		arr = []
		for i in range(10):
			for item in buckets[i]:
				arr.append(item)
			exp *= 10
	return arr

# Test array
arr = [170, 45, 75, 90, 802, 24, 2, 66]
print('Sorted array is:', radix_sort(arr))

function radixSort(arr) {
	let max_value = Math.max(...arr);
	let exp = 1;
	while (max_value // exp > 0) {
		const buckets = Array(10).fill([]);
		for (let i of arr) {
			let index = Math.floor((i / exp) % 10);
			buckets[index].push(i);
		}
		arr = [];
		for (let i = 0; i < 10; i++) {
			for (let item of buckets[i]) {
				arr.push(item);
			}
		}
		exp *= 10;
	}
	return arr;
	}

// Test array
let arr = [170, 45, 75, 90, 802, 24, 2, 66];
console.log('Sorted array is:', radixSort(arr));

public static int[] radixSort(int[] arr) {
	int max_value = Integer.MIN_VALUE;
	for (int i : arr) {
		max_value = Math.max(max_value, i);
	}
	int exp = 1;
	while (max_value / exp > 0) {
		int[][] buckets = new int[10][];
		for (int i = 0; i < arr.length; i++) {
			int index = (arr[i] / exp) % 10;
			if (buckets[index] == null) {
				buckets[index] = new int[0];
			}
			buckets[index] = Arrays.copyOf(buckets[index], buckets[index].length + 1);
			buckets[index][buckets[index].length - 1] = arr[i];
		}
		int index = 0;
		for (int i = 0; i < 10; i++) {
			if (buckets[i] != null) {
				for (int item : buckets[i]) {
					arr[index++] = item;
				}
			}
		}
		exp *= 10;
	}
	return arr;
	}

// Test array
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
System.out.println('Sorted array is: ' + Arrays.toString(radixSort(arr)));

func radixSort(arr []int) []int {
	max_value := arr[0]
	for _, val := range arr {
		max_value = max(max_value, val)
	}
	exp := 1
	for max_value/exp > 0 {
		buckets := make([][]int, 10)
		for _, val := range arr {
			index := (val / exp) % 10
			buckets[index] = append(buckets[index], val)
		}
		arr = []int{}
		for i := 0; i < 10; i++ {
			arr = append(arr, buckets[i]...)
		}
		exp *= 10
	}
	return arr
	}

// Test array
arr := []int{170, 45, 75, 90, 802, 24, 2, 66}
fmt.Println('Sorted array is:', radixSort(arr))

void radix_sort(int arr[], int n) {
	int max_value = arr[0];
	for (int i = 1; i < n; i++) {
		max_value = max(max_value, arr[i]);
	}
	int exp = 1;
	while (max_value / exp > 0) {
		int count[10] = {0};
		for (int i = 0; i < n; i++) {
			int index = (arr[i] / exp) % 10;
			count[index]++;
		}
		int output[n];
		for (int i = 1; i < 10; i++) {
			count[i] += count[i - 1];
		}
		for (int i = n - 1; i >= 0; i--) {
			int index = (arr[i] / exp) % 10;
			output[count[index] - 1] = arr[i];
			count[index]--;
		}
		for (int i = 0; i < n; i++) {
			arr[i] = output[i];
		}
		exp *= 10;
	}
	}

// Test array
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
radix_sort(arr, n);
printf('Sorted array is: ');
for (int i = 0; i < n; i++) {
	printf('%d ', arr[i]);
}
printf('\n');