please use java thanks

the arraylist code:

import java.util.Comparator;

import java.util.Iterator;

import java.util.NoSuchElementException;

import java.util.Random;

import java.util.Arrays;

public class ArrayList implements ReadonlyList

{

private Object[] array;

private int size;

public ArrayList(int capacity)

{

array = new Object[capacity];

}

public int size()

{

return size;

}

@SuppressWarnings("unchecked")

public T get(int index)

{

if (index >= size)

{

throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);

}

else

{

return (T) array[index];

}

}

public void set(int index, T value)

{

if (index >= size)

{

throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);

}

else

{

array[index] = value;

}

}

private void resize(int newCapacity)

{

Object[] original = array;

array = new Object[newCapacity];

for (int i = 0; i

{

array[i] = original[i];

}

}

public void add(T value)

{

if (size == array.length)

{

resize(size * 2);

}

array[size] = value;

size++;

}

public void addAll(T[] values)

{

for (T v : values)

{

add(v);

}

}

private void shiftRight(int index, int amount)

{

for (int k = size - 1; k >= index; k--)

{

array[k + amount] = array[k];

}

}

public void add(int index, T value)

{

if (index > size)

{

throw new IndexOutOfBoundsException(

"Index: " + index + ", Size: " + size);

}

if (size == array.length)

{

resize(size * 2);

}

shiftRight(index, 1);

array[index] = value;

size++;

}

public void addAll(int index, T[] values)

{

if (index > size)

{

throw new IndexOutOfBoundsException(

"Index: " + index + ", Size: " + size);

}

if (size + values.length > array.length)

{

resize((size + values.length) * 2);

}

shiftRight(index, values.length);

for (int k = 0; k

{

array[index + k] = values[k];

}

size += values.length;

}

public void remove()

{

if (size

{

throw new IllegalStateException("Array is empty, no item to remove!");

}

else

{

size--;

}

}

private void shiftLeft(int index, int amount)

{

for (int k = index; k + amount

{

array[k] = array[k + amount];

}

}

public void remove(int index, int count)

{

if (index + count > size)

{

throw new IndexOutOfBoundsException(

"Index: " + size + ", Size: " + size);

}

else

{

shiftLeft(index, count);

size -= count;

}

}

public void sort(Comparator c)

{

for (int i = 1; i

{

T n = get(i);

for (int j = i - 1;

j >= 0 && c.compare(n, get(j))

j--)

{

array[j + 1] = get(j);

array[j] = n;

}

}

}

public String toString()

{

if (size == 0)

{

return "[]";

}

else

{

StringBuilder stringBuilder = new StringBuilder("[");

stringBuilder.append(get(0));

for (int i = 1; i

{

stringBuilder.append(", ");

stringBuilder.append(get(i));

}

stringBuilder.append("]");

return stringBuilder.toString();

}

}

public Iterator iterator()

{

return new Iterator()

{

private int i = -1;

public boolean hasNext()

{

return i + 1

}

public T next()

{

if (!hasNext())

{

throw new NoSuchElementException();

}

i++;

return get(i);

}

};

}

public static void main(String[] args)

{

ArrayList list = new ArrayList(4);

list.addAll(new Double[] { 1.0, 1.5, 2.0, 2.5, 3.5, 4.0, 4.5, 5.0 });

for (int i = 0; i

{

System.out.println(list.get(i));

}

System.out.println();

System.out.println("Using iterator:");

Iterator iterator = list.iterator();

while (iterator.hasNext())

{

System.out.println(iterator.next());

}

System.out.println();

System.out.println("Set element 4 to 3.14:");

list.set(4, 3.14);

for (int i = 0; i

{

System.out.println(list.get(i));

}

System.out.println();

System.out.println("Insert 9.0 at position 3, and -5.0 at position 0:");

list.add(3, 9.0);

list.add(0, -5.0);

System.out.println("Insert 0.5, 1.5, 2.5 at position 1:");

list.addAll(1, new Double[] {0.5, 1.5, 2.5});

System.out.println("Insert 99.0 at position 13:");

list.add(13, 99.0);

for (int i = 0; i

{

System.out.println(list.get(i));

}

System.out.println();

System.out.println("Remove three elements from the end:");

list.remove();

list.remove();

list.remove();

for (int i = 0; i

{

System.out.println(list.get(i));

}

System.out.println();

System.out.println("Remove six elements at position 2.");

list.remove(2, 6);

for (int i = 0; i

{

System.out.println(list.get(i));

}

System.out.println();

System.out.println("Expecting exceptions:");

try

{

System.out.println(list.get(5));

System.out.println("No exception!");

}

catch(IndexOutOfBoundsException e)

{

e.printStackTrace();

}

try

{

list.set(5, 1.0);

System.out.println("No exception!");

}

catch(IndexOutOfBoundsException e)

{

e.printStackTrace();

}

try

{

list.add(6, 1.0);

System.out.println("No exception!");

}

catch(IndexOutOfBoundsException e)

{

e.printStackTrace();

}

try

{

list.addAll(6, new Double[] {1.0, 2.0, 3.0});

System.out.println("No exception!");

}

catch(IndexOutOfBoundsException e)

{

e.printStackTrace();

}

try

{

list.remove(1, 5);

System.out.println("No exception!");

}

catch(IndexOutOfBoundsException e)

{

e.printStackTrace();

}

try

{

System.out.println(list.get(-1));

System.out.println("No exception!");

}

catch(IndexOutOfBoundsException e)

{

e.printStackTrace();

}

System.out.println();

System.out.println("Remove all but the first element:");

list.remove(1, 4);

for (int i = 0; i

{

System.out.println(list.get(i));

}

System.out.println();

list.remove();

System.out.println("List should be empty:");

System.out.println("size = " + list.size());

System.out.println();

System.out.println("Expecting exception:");

try

{

list.remove();

System.out.println("No exception!");

}

catch(IllegalStateException e)

{

e.printStackTrace();

}

Random random = new Random();

ArrayList l1 = new ArrayList(100);

for (int i = 0; i

{

l1.add(random.nextInt(100));

}

System.out.println(Arrays.toString(l1.array));

l1.sort(Comparator.naturalOrder());

System.out.println(Arrays.toString(l1.array));

ArrayList l2 = new ArrayList(100000);

for (int i = 0; i

{

l2.add(random.nextInt());

}

l2.sort(Comparator.naturalOrder());

for (int i = 1; i

{

if (l2.get(i)

{

System.out.println("FAIL: " + l2.get(i - 1) + ", " + l2.get(i));

return;

}

}

System.out.println("PASS");

}

}

1Merging arrays 0 In order to accomplish our ultimate goal of sorting an array in less than O(n2) time, we need to first merge two sorted arrays in O(n) time. Download the ArrayList.java class posted on Moodle under Week 4. Your task is to replace the insertion-sort implementation of sort with a merge-sort implementation. Start by writing the following helper method: public static T merge (TI) arrl, T arr2, Comparator comp) This should accept two sorted arrays and a Comparator as input and return a sorted array with the combined contents of both arrays Write a main method to show that merge ( works. You can use either Strings or Integers to test this easily. Use Comparator examples from lecture to create your own Comparator (consider using an anonymous class in your main) method or even a lambda expression). Think about the edge cases you may run into when attempting to combine two arrays. Will they always be the same length? What happens when you have finished going through the elements of the first array, but not the second