Hint: In-place means it does not occupy extra memory for merge operation as in the standard case.

A 3-way merge sort on an array with N elements works as follows:

1. divide the array into 3 subarrays of size N/3 ; 2. recursively sort the 3 subarrays; 3. merge the 3 subarrays together.

- Find the time complexity of the 3-way merge sort. You may assume that N is a power of 3. Show your work.

- Between 3-way and 2-way merge sort, which one has better time complexity? Justify your answer.

- Write an algorithm using an appropriate data structure that implements an in-place merge sort algorithm.