Bucket Sort in Java

Bucket sort is an algorithm for sorting an array of elements that are uniformly distributed across a range. It works by dividing the range into a number of "buckets," and then distributing the elements of the array into the buckets based on their value. The elements within each bucket are then sorted using a different sorting algorithm (such as quicksort or mergesort). Finally, the elements from the buckets are concatenated back into the original array.

Here is an example of how you might implement bucket sort in Java:

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

class BucketSort {

  public static void sort(int[] array, int min, int max) {

    int bucketCount = (max - min) / array.length + 1;

    List<List<Integer>> buckets = new ArrayList<>(bucketCount);

    for (int i = 0; i < bucketCount; i++) {

      buckets.add(new ArrayList<>());

    }

    for (int i : array) {

      buckets.get((i - min) / array.length).add(i);

    }

    int k = 0;

    for (List<Integer> bucket : buckets) {

      Collections.sort(bucket);

      for (int i : bucket) {

        array[k++] = i;

      }

    }

  }

}

You can then use the sort method to sort an array as follows:

int[] array = {4, 3, 2, 1};

BucketSort.sort(array, 1, 4);

System.out.println(Arrays.toString(array)); // Outputs [1, 2, 3, 4]