What is the time complexity of this recursive function

I have a function of following form that I would like to know the time complexity of:

recursiveFunction(List<Input> list, int leftIndex, int rightIndex){

      // If Terminating condition of recursion has been met, generate appropriate output. 
      // Else, do following processing

      midIndex = (leftIndex + rightIndex) / 2

      List<Input> leftHalf = Generate_Left_Half_Of_Input_list
      List<Input> rightHalf = Generate_Right_Half_Of_Input_list

      if(!someFunction(leftHalf)){
          recursiveFunction(list, leftIndex, midIndex);
      } else if(!someFunction(rightHalf)){
          recursiveFunction(list, midIndex, rightIndex);
      } else {
          // Generate 4 lists from input list, each of which is guaranteed to be 1 / 2 size of input list _to this step / particular recursive call_
          // Call someFunction for 4 of these, if it returns false for some list generated in step above, call recursiveFunction for _that list_
          // Note that the size of input to recursiveFunction at step n + 1 is guaranteed to be 1 / 2 of what it was at step n regardless of which if / else path was followed at step n 
      }
}

Time required for someFunction is proportional to input size. i.e. someFunction requires time k For input size n, requires time k / 2 for input size n / 2.

To me, it looks like this has the time complexity of O(n log n) since the size of input is decreasing by a factor of 2 at each step and there can be at most one recursive call at each step. someFunction does require some time, but it is proportional to n, and it reduces by same factor as n at each step, so I'm assuming that that will contribute a constant to overall complexity (e.g. 2 n Log n) which will be ignored in Big-O notation.

What work have I done?

I have checked Master Theorem, I don't think it is applicable since time spent on things out of recursive function (f(n)) is not polynomial.
Recursive Tree method gives expression of 5T(n/2) + n/2, which looks like that of merge sort, which I know has complexity of O(n log n)

What is the correct answer?

Solution

Let's first establish that the non-recursive parts of the code have O(𝑛) complexity, where 𝑛 is the size of the relevant subarray, i.e. rightIndex - leftIndex + 1. We can group those non-recursive parts and corresponding complexities as follows:

O(𝑛) for creating at most 6 arrays which have half the size of the input list. This includes leftHalf, rightHalf and possibly the 4 lists that are created in the final else block;
O(𝑛) for executing someFunction on at most 6 arrays (the ones mentioned in the previous bullet point);
O(1) on evaluating expressions such as (leftIndex + rightIndex) / 2, and other trivial stuff. I assume the uniform cost model here.

(The descriptions that take the place of some omitted parts of the code are somewhat ambiguous, where pseudocode instead of comments would have been preferrable, but I will assume the above applies to what you have there)

You wrote:

it looks like this has the time complexity of O(n log n) since the size of input is decreasing by a factor of 2 at each step and there can be at most one recursive call at each step.

The second part of your statement ("since...") is true, but the conclusion you get from it is wrong.

We have this recurrence relation 𝑇_𝑛:

𝑇₁ = 1
𝑇_𝑛 = O(𝑛) + 𝑇_𝑛/2 for 𝑛 > 1

If you expand the recurrent part, you get:

𝑇_𝑛 = O(𝑛) + O(𝑛/2) + O(𝑛/4) + ... = O( ∑_{𝑖=0..log𝑛} 𝑛/2^𝑖 )

This is a finite geometric series with 𝑟=1/2, making 𝑇_𝑛 = O(2𝑛) = O(𝑛)