what is the complexity of this sorting algorithm?

Question

public class SortAlgorithm {
public static void sorting(int[] A){
    quickLevel_sort(A, 0, A.length - 1);
}

private static void mergeLevel_Sort(int[] A, int begin, int end) {
    if (begin < end) {
        int middle = (begin + end) / 2;
        quickLevel_sort(A, begin, middle);
        quickLevel_sort(A, middle + 1, end);
        merge(A, begin, middle, end);
    }
}

private static void quickLevel_Sort(int[] A, int begin, int end) {
    if (begin < end) {
        int middle = partition(A, begin, end);
        mergeLevel_sort(A, begin, middle - 1);
        mergeLevel_sort(A, middle + 1, end);
    }
}}

I want to find the complexity of this function, but it isn't very clear because mergelevel and quicklevel are calling each other recursively. I hope someone can give me some tips

The "merge" function is used in merge sort to merge two sorted arrays, working in O(n) time complexity. The "partition" function, used in quicksort, selects the first element as the pivot and finds its correct location in the array, placing it there. Its complexity is also O(n).

Answer 1

Let $M(n)$ be the runtime of mergeLevel on an input of size $n$, and let $Q$ be the runtime of quickLevel on an input of size $n$.

By inspecting the code, we see that $M(n) = 2Q(\frac{n}{2}) + n$ and $Q(n) \leq n + \max_{1 \leq i < n} M(n - i) + M(i)$. We can then just substitute, and henceforth ignore $M$:

$$Q(n) \leq 2n + 2\max_{1 \leq i < n} Q(\frac{n - i}{2}) + Q(\frac{i}{2})$$

The worst case for the maximum is going to be $i = 1$, which leads us to $Q(n) = O(n^2)$.