Please answer in java, I can split up the questions if needed too. thanks!

Tasks: 1. Design an algorithm in pseudocode for in-place Insertion-Sort (implemented on an array), as discussed in class, and which is used to sort integers in increasing order. 2. Implement the Insertion-Sort algorithm you designed in #1 in your favorite programming language. 3. Implement the in-place Quicksort algorithm on an array, again, used to sort integers in increasing order, where the pivot is always chosen as the last element of the list. 4. Write an algorithm for Merge-sort that uses queues. Your algorithm should use the queue ADT that you implemented in Assignment 2 (but not the actual arrays). That is, the input to the algorithm is a queue, and when partitioning is done, two queues are created (L and G). Then, L and G are sorted recursively in the same way and merged when sorted. Note that you have already implemented the Merge algorithm that uses queues! 5. Implement your Merge-sort algorithm in your favorite programming language. 6. What are the worst and best-case time complexities in O-notation of a. Insertion-Sort? b. Quicksort? c. Merge-sort? Why? Your answer must be given based on the algorithms you implemented. 7. [2 bonus marks*] Write a program that generates an array A of n random integers, and sorts A using Insertion-Sort, Quicksort and Merge-sort. Run your program with arrays of size n = 8, 16, 32, 64, ..., 20. Keep track of the CPU time each algorithm takes to sort each of these arrays. Comment on the running times you obtained, and compare them to the complexities as discussed in class. Hint: place the CPU times you obtained on a table or a plot (or both) to interpret the results. 8. [2 bonus marks*] Implement the recursive algorithm that reverses an array, and run it on the sorted lists of Insertion-Sort, Quicksort and Merge-sort. The output should be lists sorted in decreasing order. *max 2 bonus marks for this assignment. Tasks: 1. Design an algorithm in pseudocode for in-place Insertion-Sort (implemented on an array), as discussed in class, and which is used to sort integers in increasing order. 2. Implement the Insertion-Sort algorithm you designed in #1 in your favorite programming language. 3. Implement the in-place Quicksort algorithm on an array, again, used to sort integers in increasing order, where the pivot is always chosen as the last element of the list. 4. Write an algorithm for Merge-sort that uses queues. Your algorithm should use the queue ADT that you implemented in Assignment 2 (but not the actual arrays). That is, the input to the algorithm is a queue, and when partitioning is done, two queues are created (L and G). Then, L and G are sorted recursively in the same way and merged when sorted. Note that you have already implemented the Merge algorithm that uses queues! 5. Implement your Merge-sort algorithm in your favorite programming language. 6. What are the worst and best-case time complexities in O-notation of a. Insertion-Sort? b. Quicksort? c. Merge-sort? Why? Your answer must be given based on the algorithms you implemented. 7. [2 bonus marks*] Write a program that generates an array A of n random integers, and sorts A using Insertion-Sort, Quicksort and Merge-sort. Run your program with arrays of size n = 8, 16, 32, 64, ..., 20. Keep track of the CPU time each algorithm takes to sort each of these arrays. Comment on the running times you obtained, and compare them to the complexities as discussed in class. Hint: place the CPU times you obtained on a table or a plot (or both) to interpret the results. 8. [2 bonus marks*] Implement the recursive algorithm that reverses an array, and run it on the sorted lists of Insertion-Sort, Quicksort and Merge-sort. The output should be lists sorted in decreasing order. *max 2 bonus marks for this assignment