please use java.Thanks.

The previous merge method is:

import java.util.Comparator;

import java.util.Iterator;

import java.util.NoSuchElementException;

import java.util.Random;

import java.util.Arrays;

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

{

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 static T[] merge(T[] arr1,T[] arr2,Comparator comp)

{

Object[] list=new Object[arr1.length+arr2.length];

int i=0,j=0,k=0;

while(i

{

if(comp.compare(arr1[i],arr2[j])

list[k++]=arr1[i++];

else

list[k++]=arr2[j++];

}

while(i

while(j

return (T[])list;

}

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");

}

}

3 The rest of merge-sort Once we can combine sorted arrays efficiently, the rest of merge-sort quickly falls in to place. Implement the following method to complete the sorting algorithm: public static TI] mergesort (TI] arr, Comparator