Question
I have a merge sort algorithm and it passes all the test cases.I need to calculate how many comparisons in this algorithm. At the func
I have a merge sort algorithm and it passes all the test cases.I need to calculate how many comparisons in this algorithm. At the func of def merge_sort(a) I need to return count-comparison. I am adding my algorithm below please do not change it, just add count variable to count how many comparisons in my function and return count at the merge_sort(a) function. ty!
def finalMerge(a, left_index, right_index, middle): ## Lets take copy of both left and right side of the arrays. # since they are not inclusive by thet it means edge numbers are not included, so I'm increasing the count by 1 leftPartArrayCopy = a[left_index:middle + 1] rightPartArrayCopy = a[middle+1:right_index+1]
# These are the indexes of left and right part of the arrays , to keep #track fo the loops IndexOfLeftCopy = 0 IndexOfRightCopy = 0 IndexOfSortedCopy = left_index
# Lets Iterate through both the copies , until we have reached end of one part while IndexOfLeftCopy < len(leftPartArrayCopy) and IndexOfRightCopy < len(rightPartArrayCopy):
# suppose we find a element smaller in left part of the array , we move it to final sorted list and move pointer by 1 if leftPartArrayCopy[IndexOfLeftCopy] <= rightPartArrayCopy[IndexOfRightCopy]: a[IndexOfSortedCopy] = leftPartArrayCopy[IndexOfLeftCopy] IndexOfLeftCopy = IndexOfLeftCopy + 1 count = count+1 # suppose we find a element smaller in right part of the array, we move it to final sorted list and increment pointer by 1 else: a[IndexOfSortedCopy] = rightPartArrayCopy[IndexOfRightCopy] IndexOfRightCopy = IndexOfRightCopy + 1
# increment the sorted part. IndexOfSortedCopy = IndexOfSortedCopy + 1
# By this point we have ran out of the elements in right or left side of the array and copy remaining elements to sorted array part. while IndexOfLeftCopy < len(leftPartArrayCopy): a[IndexOfSortedCopy] = leftPartArrayCopy[IndexOfLeftCopy] IndexOfLeftCopy = IndexOfLeftCopy + 1 IndexOfSortedCopy = IndexOfSortedCopy + 1
while IndexOfRightCopy < len(rightPartArrayCopy): a[IndexOfSortedCopy] = rightPartArrayCopy[IndexOfRightCopy] IndexOfRightCopy = IndexOfRightCopy + 1 IndexOfSortedCopy = IndexOfSortedCopy + 1
def merge_sort_recursive(a, leftPart, rightPart): if leftPart >= rightPart: return
middlePart = (leftPart + rightPart)//2 merge_sort_recursive(a, leftPart, middlePart) merge_sort_recursive(a, middlePart + 1, rightPart) finalMerge(a, leftPart, rightPart, middlePart) def merge_sort(a): merge_sort_recursive(a, 0, len(a) -1) return count
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started