 ## Problem 1

The idea of quicksort is very easy, and the main difficulty lies in how to implement it with a constant number of extra spaces, i.e., to make it in-place. There is no such an issue for linked lists. Implement in-place quicksort for ListOnArray.java. You may use the first element as the pivot and use any partition scheme.

## Problem 2

Given a complete binary search tree of n nodes, where the element in one of its nodes has been changed. Restore the complete binary search tree. Your algorithm should run in time O(n) time.
You are not allowed to modify class Node or create new nodes (calling the constructor of class Node in your algorithm). No points if you do either of them.

You get 10 bonus points if your algorithm takes less than O(n) time in the best case.

## Problem 3

Given a max heap of n nodes, stored as an array. The element in one of its nodes has been changed. Find this element in O(n) time, and restore the max heap in O(log n) time.
In example (a), the changed element might be 6 (from 8) or 7 (from 4). It is fine you return either of them. On the other hand, the changed element in example (b) must be 4 (from some number between 9 and 7).

## Problem 4 [Optional]

Given k arrays of students, each of which is sorted according to the grades, the task is to merge these arrays into a single sorted array.
For example, if k = 3 and the three input arrays are:

• (Angelina Jolie, 60), (Leonardo DiCaprio, 60), (Charlize Theron, 60);
• (Eason Chan, 40), (Denise Ho, 60), (Jennifer Chan, 70), (Joey Yung, 80), (Kay
Tse, 90), (Cheung Jacky, 95); and
• (Winnie, 0), (Mickey, 90), (Teddy, 95), (Peppa, 100),

then the result should be
(Winnie, 0), (Eason Chan, 40), (Angelina Jolie, 60), (Leonardo DiCaprio, 60), (Charlize Theron, 60), (Denise Ho, 60), (Jennifer Chan, 70), (Joey Yung, 80), (Kay Tse, 90), (Mickey, 90), (Cheung Jacky, 95), (Teddy, 95), (Peppa, 100)

Write two different algorithms to do this task. More requirements:

• Your algorithms need to be stable,i.e., of two students with the same grade, the student from an earlier array should appear first. In the example above, Charlize Theron is put before Denise Ho because they are from the first and second input arrays respectively. Likewise, Mickey comes after Kay Tse.

• Your algorithms have to run in O(n log k) time, where n is the total numbers of students.