Practice Test 3

In the recursive merge sort code below, how does the algorithm handle the input array in recursive steps?

import java.util.*;

public class Sorter {

    public static int[] mergeSort(int[] nums) {

        // Base case: length 0 or 1 is already sorted

        if (nums.length <= 1) {

            return nums;

        }

        int mid = nums.length / 2;

        // Split into two halves

        int[] left = Arrays.copyOfRange(nums, 0, mid);

        int[] right = Arrays.copyOfRange(nums, mid, nums.length);

        // Recursively sort each half

        left = mergeSort(left);

        right = mergeSort(right);

        // Merge sorted halves

        return merge(left, right);

    }

    private static int[] merge(int[] left, int[] right) {

        // Recursively merges are not required here; focus is on mergeSort recursion

        int[] result = new int<u>left.length + right.length</u>;

        int i = 0, j = 0, k = 0;

        while (i < left.length && j < right.length) {

            if (left<u>i</u> <= right<u>j</u>) result<u>k++</u> = left<u>i++</u>;

            else result<u>k++</u> = right<u>j++</u>;

        }

        while (i < left.length) result<u>k++</u> = left<u>i++</u>;

        while (j < right.length) result<u>k++</u> = right<u>j++</u>;

        return result;

    }

}

Assume nums starts as {8, 3, 6, 2}.

For the recursive factorial method below, what is the time complexity of the given recursive algorithm?

public class MathUtil {

    public static int factorial(int n) {

        if (n == 0) {

            return 1;

        }

        return n * factorial(n - 1);

    }

}