please i need help, this is Java:

You have to implement your own LinkedList class in this homework (either Doubly or Singly is fine). And you have to implement your own Queue data structure (either an Array-based or a LinkedList-based queue is fine).

Please implement the MergeSort algorithm on a LinkedList object, as we learned in the class. The logic idea is shown below. If you failed to follow this logic idea, you could get a zero in this homework.

1, Enqueue all data elements of the linked list, with each element wrapped up and enqueued as a separate one-node list object.

2, while there is more than 1 items in Queue

a. dequeue and assign to a linked list reference sublist1

b. dequeue again and assign to another linked list reference sublist2

c. walk through sublist1 and sublist2 and merge them into a larger sorted listed tempList, with tempList = ( sublist1 merged with sublist2 )

d. equeue tempList

3, dequeue your sorted linked list.

Please implement the InsertionSort algorithm on a LinkedList object, as we learned in the class.

Please write a method boolean isSorted(LinkedList B) to verify whether the LinkedList B is correctly sorted in an ascending order.

boolean isSorted(LinkedList B)

Note: isSorted(LinkedList B) returns true, if B has been sorted in ascending order. Otherwise it returns false.

Note: your isSorted(LinkedList B) has to run in the time complexity of O(n), where n is the size of the input LinkedList. In other words, you scan the input list B once, you should know whether it is sorted or not.

In your main() method in a source file named Tester.java, please create an empty LinkedList A, then please use the Java Random class to generate a sequence S of 20,000 integers, which range between 0 and 3,000,000. You have to insert each element of S into the LinkedList A, with each list node in A holding one integer.

NOTE PLEASE READ: For those who have an old and slow machine, sorting two 20,000 integers maybe too time-consuming. You can generate 2000 integers and sort them, instead of 20,000.

In your main() method of the Tester.java file, please create another separate LinkedList object A2, which contains the same set of integers as A does.

Please invoke the method of your MergeSort() algorithm implementation on the input list A in the separate java file Tester.java. Then call isSorted(A) to verify whether A is correctly sorted.

Please invoke the method of your InsertionSort() algorithm implementation on the input list A2 in the separate java file Tester.java. Then call isSorted(A2) to verify whether A2 is correctly sorted.

Your main() method of your Tester class should perform the operations described in the below,

// First Create A and A2,

// Randomly generate two million integers and insert them into both A and A2.

//

//measure the time cost of merge sort

double then = System.currentTimeMillis();

A.MergeSort();

double now = System.currentTimeMillis();

System.out.println(Time cost in milliseconds for mergesort two million elements are: + (now then));

System.out.println( isSorted(A) ); //verify that your merge sort implementation works.

//measure the time cost of insertion sort

then = System.currentTimeMillis();

A2.InsertionSort();

now = System.currentTimeMillis();

System.out.println(Time cost in milliseconds for insertionsort two million elements are: + (now then));

System.out.println( isSorted(A2) ); //verify that your insertion sort implementation works.

Please organize your source code so that I can compile all your source files in one folder using command, javac *.java, and run your program using command on command line, java Tester.