Sorting is a fundamental operation in programming and computer science. Whether you’re arranging numbers in order, ranking students by grades, or organizing files alphabetically, sorting makes data easy to use and analyze. One of the most interesting sorting techniques, especially when dealing with real numbers or floating-point data, is Bucket Sort.
with hands-on learning.
get the skills and confidence to land your next move.
Bucket Sort is a sorting algorithm that works by dividing elements into several groups known as “buckets.” Each bucket contains elements that fall within a particular range. Once the elements are distributed, each bucket is sorted individually — often using another sorting method like Insertion Sort — and then all the buckets are combined to form the final sorted list. This approach can be very efficient, especially when the input data is uniformly distributed over a range.
It’s often used in real-world situations such as sorting decimal numbers, floating-point values, or data that has a predictable range (like percentages, marks, or probabilities). Its strength lies in the fact that it can achieve nearly linear time complexity for well-distributed datasets, making it faster than many comparison-based algorithms like Merge Sort or Quick Sort in certain cases.
Program 1: Basic Bucket Sort in GoLang
This is the simplest form of Bucket Sort. It divides the array into buckets, sorts each bucket individually using the built-in sorting function, and then merges them all back into a single sorted array.
package main
import (
"fmt"
"sort"
)
func bucketSort(arr []float64) []float64 {
n := len(arr)
if n <= 0 {
return arr
}
buckets := make([][]float64, n)
for _, num := range arr {
index := int(num * float64(n))
if index >= n {
index = n - 1
}
buckets[index] = append(buckets[index], num)
}
for i := 0; i < n; i++ {
sort.Float64s(buckets[i])
}
var result []float64
for i := 0; i < n; i++ {
result = append(result, buckets[i]...)
}
return result
}
func main() {
numbers := []float64{0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51}
fmt.Println("Original array:", numbers)
sorted := bucketSort(numbers)
fmt.Println("Sorted array:", sorted)
}This program creates several buckets based on the range of the input numbers. Each element is placed in the right bucket, the buckets are sorted using Go’s built-in sort.Float64s function, and then the results are merged. This method is easy to understand and implement, especially for beginners who are just getting started with sorting algorithms.
Program 2: Bucket Sort Using Insertion Sort
In some cases, instead of using Go’s built-in sort, we can manually sort each bucket using Insertion Sort. This gives us more control and helps beginners understand the internal sorting process better.
package main
import "fmt"
func insertionSort(arr []float64) {
for i := 1; i < len(arr); i++ {
key := arr[i]
j := i - 1
for j >= 0 && arr[j] > key {
arr[j+1] = arr[j]
j--
}
arr[j+1] = key
}
}
func bucketSort(arr []float64) []float64 {
n := len(arr)
if n <= 0 {
return arr
}
buckets := make([][]float64, n)
for _, num := range arr {
index := int(num * float64(n))
if index >= n {
index = n - 1
}
buckets[index] = append(buckets[index], num)
}
for i := 0; i < n; i++ {
insertionSort(buckets[i])
}
var result []float64
for i := 0; i < n; i++ {
result = append(result, buckets[i]...)
}
return result
}
func main() {
numbers := []float64{0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68}
fmt.Println("Original array:", numbers)
sorted := bucketSort(numbers)
fmt.Println("Sorted array:", sorted)
}This version of Bucket Sort gives a deeper look into the algorithm’s behavior. Instead of relying on Go’s built-in functions, we manually implement Insertion Sort inside each bucket. It’s a great exercise for beginners to understand how different sorting methods can work together to produce efficient results.
Program 3: Bucket Sort with Integer Inputs
So far, we have sorted floating-point numbers, but Bucket Sort can also work for integer values when adjusted properly. This version demonstrates how to sort integers by scaling them into appropriate buckets.
package main
import (
"fmt"
"sort"
)
func bucketSortInts(arr []int) []int {
n := len(arr)
if n <= 0 {
return arr
}
max := arr[0]
for _, v := range arr {
if v > max {
max = v
}
}
buckets := make([][]int, n)
for _, num := range arr {
index := num * (n - 1) / max
buckets[index] = append(buckets[index], num)
}
for i := 0; i < n; i++ {
sort.Ints(buckets[i])
}
var result []int
for i := 0; i < n; i++ {
result = append(result, buckets[i]...)
}
return result
}
func main() {
numbers := []int{42, 32, 33, 52, 37, 47, 51}
fmt.Println("Original array:", numbers)
sorted := bucketSortInts(numbers)
fmt.Println("Sorted array:", sorted)
}Here, we adjust the logic to work with integers by scaling their values based on the maximum element. It’s a handy modification when dealing with integer data, allowing the same bucket-based principle to work effectively.
Program 4: Recursive Bucket Sort
For those who like recursion, this version shows how to implement Bucket Sort recursively. It repeatedly divides the data into smaller buckets until each bucket contains only one or two elements.
package main
import (
"fmt"
)
// recursiveBucketSort safely sorts floats in [0,1)
func recursiveBucketSort(arr []float64) []float64 {
if len(arr) <= 1 {
return arr
}
n := len(arr)
buckets := make([][]float64, n)
// Find min and max to normalize values if needed
min, max := arr[0], arr[0]
for _, num := range arr {
if num < min {
min = num
}
if num > max {
max = num
}
}
// If all numbers are the same, return as is to prevent infinite recursion
if min == max {
return arr
}
// Distribute elements into buckets
for _, num := range arr {
// normalize to [0,1)
index := int((num - min) / (max - min) * float64(n))
if index >= n {
index = n - 1
}
buckets[index] = append(buckets[index], num)
}
var result []float64
for i := 0; i < n; i++ {
// Only recurse if bucket has more than 1 element
if len(buckets[i]) > 1 {
buckets[i] = recursiveBucketSort(buckets[i])
}
result = append(result, buckets[i]...)
}
return result
}
func main() {
numbers := []float64{0.25, 0.36, 0.58, 0.41, 0.29, 0.22, 0.45, 0.79, 0.01, 0.69}
fmt.Println("Original array:", numbers)
sorted := recursiveBucketSort(numbers)
fmt.Println("Sorted array (recursive):", sorted)
}This recursive version is interesting because it sorts each bucket by calling itself until the buckets are small enough to be naturally sorted. Beginners who already understand recursion will find this approach fun to experiment with and easy to follow once they grasp the logic.
Frequently Asked Questions (FAQ)
Here are some common questions learners often ask when studying Bucket Sort in GoLang.
Q1: What is the main idea behind Bucket Sort?
Bucket Sort divides elements into multiple groups or “buckets” based on their value range, sorts each bucket individually, and then combines them to form a sorted list.
Q2: When is Bucket Sort most efficient?
It works best when the data is uniformly distributed and falls within a known range, such as numbers between 0 and 1 or percentages.
Q3: Is Bucket Sort a stable sorting algorithm?
Yes, if the sorting method used within the buckets (like Insertion Sort) is stable, then Bucket Sort as a whole will also be stable.
Q4: What is the time complexity of Bucket Sort?
In the best case, the time complexity can be O(n + k), where n is the number of elements and k is the number of buckets. In the worst case, it can degrade to O(n²) if all elements land in a single bucket.
Q5: Can I use Bucket Sort for strings or characters?
While Bucket Sort is mainly designed for numeric values, with modifications, it can also be adapted for strings, especially when sorting based on ASCII values or string lengths.
Conclusion
Bucket Sort is a beautiful example of how smart data grouping can make sorting faster and more intuitive. It’s a powerful algorithm for datasets that are evenly distributed across a range, and its simplicity makes it easy to implement in GoLang. By experimenting with versions that use loops, recursion, and custom sorting functions, you can get a deep understanding of how sorting algorithms work under the hood.
The key takeaway is that Bucket Sort is not just about sorting — it’s about learning how to divide and conquer data efficiently. With practice, you’ll soon find that writing and modifying such algorithms in GoLang feels as natural as writing any other program. Keep coding, keep exploring, and you’ll continue to unlock the beauty hidden within algorithms like this one.
