Algorithm Speed (2.00) :

Array Size (100) :

Bucket Sort :

Author(s) : E. J. Isaac and R. C. Singleton Date : 1956

Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm or by recursively applying the bucket sorting algorithm. It is a distribution sort, a generalization of pigeonhole sort, and is most effective when the input is uniformly distributed over a range.

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

def bucket_sort(arr):
	if len(arr) == 0:
		return arr
	min_val, max_val = min(arr), max(arr)
	bucket_count = len(arr)
	buckets = [[] for _ in range(bucket_count)]
	for num in arr:
		index = int((num - min_val) / (max_val - min_val + 1) * bucket_count)
		buckets[index].append(num)
	res = []
	for bucket in buckets:
		bucket.sort()
		res.extend(bucket)
	return res

function bucketSort(arr) {
	if (arr.length === 0) return arr;
	let min = Math.min(...arr);
	let max = Math.max(...arr);
	let bucketCount = arr.length;
	let buckets = Array.from({ length: bucketCount }, () => []);
	for (let i = 0; i < arr.length; i++) {
		let index = Math.floor(((arr[i] - min) / (max - min + 1)) * bucketCount);
		buckets[index].push(arr[i]);
	}
	let res = [];
	for (let i = 0; i < buckets.length; i++) {
		buckets[i].sort((a, b) => a - b);
		res.push(...buckets[i]);
	}
	return res;
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public static void bucketSort(float[] arr) {
	int n = arr.length;
	if (n <= 0) return;
	List<Float>[] buckets = new ArrayList[n];
	for (int i = 0; i < n; i++) {
		buckets[i] = new ArrayList<Float>();
	}
	for (int i = 0; i < n; i++) {
		int idx = (int) arr[i] * n;
		buckets[idx].add(arr[i]);
	}
	for (int i = 0; i < n; i++) {
		Collections.sort(buckets[i]);
	}
	int index = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < buckets[i].size(); j++) {
			arr[index++] = buckets[i].get(j);
		}
	}
}

import "sort"

func bucketSort(arr []float64) {
	n := len(arr)
	if n <= 0 {
		return
	}
	buckets := make([][]float64, n)
	for i := 0; i < n; i++ {
		idx := int(arr[i] * float64(n))
		buckets[idx] = append(buckets[idx], arr[i])
	}
	for i := 0; i < n; i++ {
		sort.Float64s(buckets[i])
	}
	index := 0
	for i := 0; i < n; i++ {
		for j := 0; j < len(buckets[i]); j++ {
			arr[index] = buckets[i][j]
			index++
		}
	}
}

#include <stdlib.h>

struct Node {
	float data;
	struct Node* next;
};

void bucketSort(float arr[], int n) {
	struct Node** buckets = (struct Node**)calloc(n, sizeof(struct Node*));
	for (int i = 0; i < n; i++) {
		int idx = n * arr[i];
		struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
		newNode->data = arr[i];
		newNode->next = NULL;
		struct Node* curr = buckets[idx];
		struct Node* prev = NULL;
		while (curr != NULL && curr->data <= arr[i]) {
			prev = curr;
			curr = curr->next;
		}
		if (prev == NULL) {
			newNode->next = buckets[idx];
			buckets[idx] = newNode;
		} else {
			newNode->next = curr;
			prev->next = newNode;
		}
	}
	int index = 0;
	for (int i = 0; i < n; i++) {
		struct Node* curr = buckets[i];
		while (curr != NULL) {
			arr[index++] = curr->data;
			struct Node* temp = curr;
			curr = curr->next;
			free(temp);
		}
	}
	free(buckets);
}