1
$\begingroup$

I'm trying to analyse the time and space complexity of the following algorithm, which is essentially a hybrid of a merge and selection sort. The algorithm is defined as follows:

def hybrid_merge_selection(L, k = 0):
    N = len(L)
    if N == 1:
        return L
    elif N <= k:
        return selection_sort(L)
    else:
        left_sublist = hybrid_merge_selection(L[:N // 2])
        right_sublist = hybrid_merge_selection(L[N // 2:])
        return merge(left_sublist, right_sublist)

My thinking is that the worst case scenario occurs when $k$ is extremely large, which means that the insertion sort algorithm is always applied resulting in a time complexity of $O(n^{2})$, where $n$ is the length of the list and the best case scenario occurs when $N$ when $k == 0$, so the merge sort algorithm is only applied resulting in a time complexity of $O(n\log_{2}n)$. However, could somebody give me a more detailed and mathematical explanation of the time complexity, for all scenarios, namely worst, best, average.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.