Time Complexity Of A 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(rightIndex <= leftIndex){
          return new ArrayList<>(); 
      }

      if(rightIndex = leftIndex + 1){
          return list;
      }

      midIndex = (leftIndex + rightIndex) / 2

      List<Input> leftHalf = list.sublist(left, mid)
      List<Input> rightHalf = list.sublist(mid, right)

      if(!someFunction(leftHalf)){
          recursiveFunction(list, leftIndex, midIndex);
      } else if(!someFunction(rightHalf)){
          recursiveFunction(list, midIndex, rightIndex);
      } else {
          leftMid = leftIndex + ((midIndex - leftIndex) / 2)
          rightMid = midIndex + ((rightIndex - midIndex) / 2)
          List l1 = leftHalf.sublist(left, leftMid);
          List l2 = leftHalf.sublist(leftMid, mid);
          List r1 = rightHalf.sublist(mid, rightMid);
          List r2 = rightHalf.sublist(rightMid, right);

          List set1 = new ArrayList<>(l1).addAll(new ArrayList<>(r1))
          List set2 = new ArrayList<>(l1).addAll(new ArrayList<>(r2))
          List set3 = new ArrayList<>(l2).addAll(new ArrayList<>(r1))
          List set4 = new ArrayList<>(l2).addAll(new ArrayList<>(r2))

          if(!someFunction(set1)){
              recursiveFunction(set1, 0, set1.size() - 1);
          } else if(!someFunction(set2)){
              recursiveFunction(set2, 0, set2.size() - 1);
          } if(!someFunction(set3)){
              recursiveFunction(set3, 0, set3.size() - 1);
          } else {
              recursiveFunction(set4, 0, set4.size() - 1);
          } 
      }
}

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. Time required to create sublists or time required to merge lists is much smaller than Time required for someFunction and can be ignored.

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 (i.e. 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 time complexity of this function?

The time complexity of the function is O(n) where n is the size of the input list segment.