As described in Section $21\mathrm{.}5$ of your textbook, it is possible to make the heap sort algorithm more efficient by writing a method that will build a heap in place using the array to be sorted. Implement such a method and rewrite the heap sort algorithm to make use of it$.$

Show test cases for various inputs, including sorted and unsorted inputs.