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)
        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.


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.