(JAVA) Part #1: Shellsort using Insertion Sort as the inner sort

Use a random number generator (Math.random or java.util.Random) to create an integer array of size 100 containing possible values between zero and 999. Perform an initial sort using bucket sort into three buckets. Each bucket should have roughly the same range of values. For example, bucket one could hold values between zero and 330, bucket two could hold values between 331 and 660, and bucket three could hold values between 661 and 999. Note this does not mean the lists will be the same size the numbers are being generated randomly. Because of this, you will not be able to use arrays for the buckets. You should use a more flexible data structure like an ArrayList or a LinkedList.

The next phase then requires you to sort each of the three buckets. For this you should use Insertion sort. You can copy the example code for Insertion sort from Blackboard and incorporate it into your program as a method. The insertion sort method requires a double array as an argument. You should change the argument to Integer array and then pass each of the buckets to the insertion sort method.

After passing each of the three buckets to the insertion sort method, they will be sorted and you should reassemble the original list by appending the sorted lists together (use System.arraycopy for this).

Sample output (with a smaller list size) shown here:

original list: [552, 488, 317, 195, 441, 794, 565, 164, 710, 539, 123, 254, 277, 304, 345, 537, 721, 86, 380, 656, 361, 931, 589, 218, 737, 933, 345, 933, 791, 367]

bucket1: [317, 195, 164, 123, 254, 277, 304, 86, 218]

bucket2: [552, 488, 441, 565, 539, 345, 537, 380, 656, 361, 589, 345, 367]

bucket3: [794, 710, 721, 931, 737, 933, 933, 791]

bucket1 after sort: [86, 123, 164, 195, 218, 254, 277, 304, 317]

bucket2 after sort: [345, 345, 361, 367, 380, 441, 488, 537, 539, 552, 565, 589, 656]

bucket3 after sort: [710, 721, 737, 791, 794, 931, 933, 933]

original list after reassembly: [86, 123, 164, 195, 218, 254, 277, 304, 317, 345, 345, 361, 367, 380, 441, 488, 537, 539, 552, 565, 589, 656, 710, 721, 737, 791, 794, 931, 933, 933]