ANSWER QUESTION 6 ONLY!! 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.