1. (40pt)  Debug HeapSort.java so it works correctly. Use comments to document what bug(s) you have fixed. And note that you should not make major changes to the code, or in other words, you should not simply replace it with some code you download from the web. Whenever you are unsure about whether a change is considered "major", ask me.

2. (20pt) Write a method sort(boolean elements[]) which sorts an array of boolean values so that all false elements precede the true elements.

• The worst case complexity of the method must be O(N) or better.
• The method may only use constant extra space, i.e. it may not use a temporary array.

Test the method with arrays consist of

• only true elements
• only false elements
• a mixture of true and false elements

3. (+30pt)  Redo Exercise 2 using a different algorithm which still satisfies the requirements of linear complexity and constant extra space.

4. Turn in all the source code files through CSNS.