Sorting Algorithm - Bucket Sort

Bucket Sort is well-suited for sorting numbers in the range of 0~100, but its efficiency decreases when dealing with data that has a wide value range.

Algorithm Steps

Create n empty buckets based on requirements
Traverse the input array to find the maximum and minimum values
For each element num, calculate bucket index using formula: floor((num - min) / n)
If a bucket already contains elements, maintain elements in sorted order (using linked list)
Repeat steps 3-4 until all elements are distributed
Concatenate all buckets' linked lists and output the sorted array

package main

import (
    "fmt"
    "math"
)

func main() {
    data := []int{111, 9, 2, 4, 9, 3, 3, 5, 7, 1, 8, 2, 11, 22, 99, 192}
    fmt.Println(BucketSort(data, 4))
}

func BucketSort(data []int, buckets int) []int {
    if len(data) == 0 {
        return data
    }

    // Find min and max values
    min, max := data[0], data[0]
    for _, num := range data {
        if num < min {
            min = num
        }
        if num > max {
            max = num
        }
    }

    bucketChunk := (max - min + 1) / buckets
    bucketLinks := make([]*LinkList, buckets)

    // Distribute numbers into buckets
    for _, num := range data {
        // Find target bucket
        bucketIndex := int(math.Floor(float64((num - min) / bucketChunk)))
        
        if bucketLinks[bucketIndex] == nil {
            bucketLinks[bucketIndex] = &LinkList{}
        }
        bucketLinks[bucketIndex].insertSorted(num)
    }

    // Merge all buckets
    index := 0
    sortedData := make([]int, len(data))
    for _, bucket := range bucketLinks {
        if bucket == nil {
            continue
        }
        
        current := bucket.head
        for current != nil {
            sortedData[index] = current.data
            index++
            current = current.next
        }
    }
    return sortedData
}

type LinkList struct {
    head *Node
}

type Node struct {
    data int
    next *Node
}

func (ll *LinkList) insertSorted(num int) {
    if ll.head == nil || ll.head.data > num {
        ll.head = &Node{num, ll.head}
        return
    }

    current := ll.head
    for current.next != nil && current.next.data <= num {
        current = current.next
    }
    current.next = &Node{num, current.next}
}