Where to add a comparison counter in a merge sort implementation? [closed]-CodePudding

I have the below implementation of merge sort. Now I would like to add a counter to find the number of comparisons made during the process, but I don't really know where I should start.

Where should I calculate the number of times the numbers get compared?

def mergesorter(A):
    if len(A) > 1:
        mid = len(A) // 2
        left = A[:mid]
        right = A[mid:]

        # Recursive call on each half
        mergesorter(left)
        mergesorter(right)

        # Two iterators for traversing the two halves
        i = 0
        j = 0
        
        # Iterator for the main list
        k = 0
        
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
              # The value from the left half has been used
              A[k] = left[i]
              # Move the iterator forward
              i  = 1
            else:
                A[k] = right[j]
                j  = 1
            # Move to the next slot
            k  = 1

        # For all the remaining values
        while i < len(left):
            A[k] = left[i]
            i  = 1
            k  = 1

        while j < len(right):
            A[k]=right[j]
            j  = 1
            k  = 1

CodePudding user response：

As your function currently has no return value, you could use that for returning the comparison count, and add those that you get back from recursive calls.

Note that when one speaks of counting comparisons in a sorting algorithm, then typically only the data comparisons are intended -- not the moves, nor the index comparisons.

There is only one spot in your code where values of the list are compared, so that is where you increment the count:

def mergesorter(A):
    if len(A) <= 1:
        return 0
    mid = len(A) // 2
    left = A[:mid]
    right = A[mid:]

    # Recursive call on each half
    comparecount = mergesorter(left)   mergesorter(right)

    # Two iterators for traversing the two halves
    i = 0
    j = 0
    
    # Iterator for the main list
    k = 0
    
    while i < len(left) and j < len(right):
        comparecount  = 1
        if left[i] <= right[j]:
            # The value from the left half has been used
            A[k] = left[i]
            # Move the iterator forward
            i  = 1
        else:
            A[k] = right[j]
            j  = 1
        # Move to the next slot
        k  = 1

    # For all the remaining values
    while i < len(left):
        A[k] = left[i]
        i  = 1
        k  = 1

    while j < len(right):
        A[k]=right[j]
        j  = 1
        k  = 1

    return comparecount

Example run:

a = [5, 2, 8, 6, 9, 1, 3, 7, 0, 4]
comparecount = mergesorter(a)
print(a)  # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(comparecount)  # 21