Bucket Sort using Linked Lists

Question

I'm trying to implement bucket sort in Java in order to sort an array of integers. I'm am trying to use Linked Lists as my buckets but am having some trouble understanding how to do so. Could anyone provide an implementation?

I've been provided this algorithm, but it doesn't make much sense to me:

Answer 1

Since you have no code to analyze, I will give a written out answer. Create a Bucket class which will contain of range between two numbers (0-9, 10-19, etc.), a insert method (which inserts in order), and contain an empty array. Then create a List of Buckets as so:

Loop through input list and insert each number into the appropriate Bucket inside the Bucket List. As you insert values, it will sort for you. Finally, get all Bucket's arrays and lump then together for the output list.

Here is a step by step process off of Wikipedia:

1. Set up an array of initially empty "buckets".
2. Scatter: Go over the original array, putting each object in its bucket.
3. Sort each non-empty bucket.
4. Gather: Visit the buckets in order and put all elements back into the original array.

This is the algorithm you were provided:

This simple translates to:

1. A is the input array which you must sort
2. n is the length of the input array A
3. You must insert all elements of input array A into your list of Buckets B
4. Now order each Bucket in the Bucket's list B.
5. Create a new list/array to return which will be all ordered Bucket's lists.

NOTE: Step 4 can actually happen as you do step 3 based on your implementation.

This algorithm does not dive into the intricate details which you'll have to code. It is just a simple guide to help you get started.