We're about to dive into the elite squad of linear-time sorting algorithms:
✅ Bucket Sort
✅ Radix Sort

These are non-comparison-based sorting algorithms, which means they bypass the O(n log n) limit that comparison sorts (like Merge, Quick, Heap) are stuck with.

They don’t compare elements directly — instead, they group, bucket, or digit-slice their way to order like absolute sorting wizards.

Let’s roll 💪

---

🎯 Linear-Time Sorting: Bucket Sort & Radix Sort

“Why compare elements pairwise like a peasant, when I can exploit structure and sort like a god?”
— Bucket & Radix Sort, probably

---

🧠 Wait — What’s “Linear-Time Sorting”?

These algorithms run in O(n) under certain conditions. That’s right — faster than Merge Sort, Quick Sort, even Heap Sort.

The catch? They:

• Require structure (like bounded ranges or digit-based representation)

• Aren’t general-purpose

• Work best on integers or floats (not strings or arbitrary objects)

---

🪣 Bucket Sort

🧃 Vibe:

“Divide into buckets, sort each one, then combine them all back like a delicious smoothie.”

---

✅ Ideal For:

• Floating-point numbers

• Uniformly distributed values

• Small ranges

• Sorting grades, probabilities, rainfall data, etc.

---

🔢 Time Complexity:

• Best: O(n)

• Average: O(n + k) (k = number of buckets)

• Worst: O(n²) — if everything ends up in one bucket 🙃

---

🛠️ Java Example (Bucket Sort for floats 0.0 to 1.0)

java
CopyEdit
import java.util.*;

public class BucketSort {
    public void sort(float[] arr) {
        int n = arr.length;
        if (n <= 0) return;

        // 1. Create empty buckets
        List<Float>[] buckets = new List[n];
        for (int i = 0; i < n; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 2. Distribute elements into buckets
        for (float value : arr) {
            int index = (int)(value * n);
            buckets[index].add(value);
        }

        // 3. Sort individual buckets
        for (List<Float> bucket : buckets) {
            Collections.sort(bucket);
        }

        // 4. Concatenate all buckets back into arr
        int idx = 0;
        for (List<Float> bucket : buckets) {
            for (float value : bucket) {
                arr[idx++] = value;
            }
        }
    }

    public static void main(String[] args) {
        float[] arr = {0.42f, 0.32f, 0.23f, 0.52f, 0.25f, 0.47f, 0.51f};

        new BucketSort().sort(arr);

        System.out.println("Sorted array:");
        for (float v : arr) {
            System.out.print(v + " ");
        }
    }
}

---

✅ Pros:

• Super fast when data is uniform

• Easy to implement

• Very low overhead

❌ Cons:

• Only works when range is known

• Not great with skewed or clustered data

• Depends heavily on bucket logic and how well it spreads

---

🎯 Radix Sort

🧃 Vibe:

“I don’t sort numbers — I sort their digits, one at a time, from least to most significant. Like peeling an onion. But cleaner.”

---

✅ Ideal For:

• Integers

• Strings of equal length

• Sorting large numbers FAST

---

🔢 Time Complexity:

• O(nk)

  • n = number of elements

  • k = number of digits

• Better than O(n log n) if k is small (e.g., base 10, max 5-digit numbers)

---

🛠️ Java Example (Radix Sort for positive integers)

java
CopyEdit
public class RadixSort {

    public void sort(int[] arr) {
        int max = getMax(arr);

        // Sort by each digit (place: 1s, 10s, 100s, etc.)
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countSort(arr, exp);
        }
    }

    private void countSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10]; // base 10 digits

        // Count occurrences of digits
        for (int i = 0; i < n; i++) {
            int digit = (arr[i] / exp) % 10;
            count[digit]++;
        }

        // Cumulative count
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // Build output array
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[--count[digit]] = arr[i];
        }

        // Copy back to original
        System.arraycopy(output, 0, arr, 0, n);
    }

    private int getMax(int[] arr) {
        int max = arr[0];
        for (int num : arr) {
            if (num > max) max = num;
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};

        new RadixSort().sort(arr);

        System.out.println("Sorted array:");
        for (int v : arr) {
            System.out.print(v + " ");
        }
    }
}

---

✅ Pros:

• Consistent performance for fixed-length numbers

• Great for big data, large ranges, and sorting billions of IDs

• Outperforms comparison-based sorts in specific use cases

❌ Cons:

• Doesn’t work for floating point (without tricks)

• Not in-place unless you optimize memory

• Not comparison-based, so not always general-purpose

---

🧠 Bucket vs Radix at a Glance

---

🧠 TL;DR (Too Long, Didn’t Linear-Sort)

• Bucket Sort → Divide values into buckets, sort each one
  ✅ Great for floats
  ✅ Fast if data is uniform
  ❌ Not general-purpose

• Radix Sort → Sort numbers by digit, from least to most significant
  ✅ Works for integers
  ✅ O(nk) time
  ❌ Doesn’t handle floats directly

---

🎓 Final Thoughts from the Sorting Galaxy

If Quick Sort is the reliable track star, and Merge Sort is the straight-A perfectionist, then Bucket and Radix Sort are the quirky geniuses who find loopholes in Big-O and just break the game.

Use them when:

• You know your input well

• You want that sweet O(n) time

• You’re okay giving up general-purpose flexibility