please use java. Thanks.

the ArrayList code is:

import java.util.Comparator; import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Random; import java.util.Arrays; 

import java.util.Iterator; public interface ReadonlyList { T get(int index); int size(); Iterator iterator(); }

 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 = 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  size) { throw new IndexOutOfBoundsException( "Index: " + size + ", Size: " + size); } else { shiftLeft(index, count); size -= count; } } public void sort(Comparator c) { for (int i = 1; i = 0 && c.compare(n, get(j))  
public static Object[] mergesort(Object[] arr, Comparator comp)
 
  1 Merging arrays 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