Problems tagged with "mergesort"

True or False: the best case time complexity of mergesort is \(\Theta(n)\).

Suppose mergesort is called on an array of size \(n\). In total, how many calls to merge are made over all calls to mergesort?

Consider the modification of mergesort shown below, where one of the recursive calls has been replaced by an in-place version of selection_sort. Recall that selection_sort takes \(\Theta(n^2)\) time.

def kinda_mergesort(arr):
    """Sort array in-place."""
    if len(arr) > 1:
        middle = math.floor(len(arr) / 2)
        left = arr[:middle]
        right = arr[middle:]
        mergesort(left)
        selection_sort(right)
        merge(left, right, arr)

What is the time complexity of kinda_mergesort?

Consider the code for mergesort and merge where a new print-statement has been added to merge:

def mergesort(arr):
    """Sort array in-place."""
    if len(arr) > 1:
        middle = math.floor(len(arr) / 2)
        left = arr[:middle]
        right = arr[middle:]
        mergesort(left)
        mergesort(right)
        merge(left, right, arr)

def merge(left, right, out):
    """Merge sorted arrays, store in out."""
    left.append(float('inf'))
    right.append(float('inf'))
    left_ix = 0
    right_ix = 0

    for ix in range(len(out)):
        print("Here!") # <---- the newly-added line
        if left[left_ix] < right[right_ix]:
            out[ix] = left[left_ix]
            left_ix += 1
        else:
            out[ix] = right[right_ix]
            right_ix += 1

Suppose mergesort is called on an array of size \(n\). In total, how many times will "Here!" be printed?