5. Merge Sort: Pseudocode

Recursively Sort the 1st Half of input array.
Recursively Sort the 2st Half of input array.
Merge two sorted sublists into one array.
 

Roughly what is the maximum depth of recursion (the maximum number of nested recursive calls) as a function of n, the length of the input array?

 n
 log n
 sqrt(n)
 n logn
 
 The answer is log n, right?
 
 6. Consider this Java example code for merge-sort. If we are going to sort an array of n elements, in big-O notation, how many operations (worse-case/upper bound) does the mergeParts method perform when called at the top level? 

 O(n)
 O(n log n)
 O(n^2)
 Omega(n)
 
 I selected the 3rd option and got it wrong. What is the correct answer and why?