You are viewing a single comment's thread. Return to all comments →
def insertionSort(arr):#by using mergesort count = 0 if len(arr) > 1: mid = len(arr)//2 left_list = arr[:mid] right_list = arr[mid:] count = count + insertionSort(left_list) count = count + insertionSort(right_list) count = count + merge(left_list,right_list,arr) return count def merge(left_list,right_list,arr): i=0 j=0 k=0 count = 0 mid = len(arr)//2 while i
Seems like cookies are disabled on this browser, please enable them to open this website
Insertion Sort Advanced Analysis
You are viewing a single comment's thread. Return to all comments →
Just have modify mergesort and count the inversion(shift) .
def insertionSort(arr):#by using mergesort count = 0 if len(arr) > 1: mid = len(arr)//2 left_list = arr[:mid] right_list = arr[mid:] count = count + insertionSort(left_list) count = count + insertionSort(right_list) count = count + merge(left_list,right_list,arr) return count def merge(left_list,right_list,arr): i=0 j=0 k=0 count = 0 mid = len(arr)//2 while i