Count swaps required to sort an array using Insertion Sort | Stores the sorted array elements ; Function to count the number of swaps required to merge two sorted subarray in a sorted form ; Stores the count of swaps ; Function to count the total number of swaps required to sort the array ; Stores the total count of swaps required ; Find the middle index splitting the two halves ; Count the number of swaps required to sort the left subarray ; Count the number of swaps required to sort the right subarray ; Count the number of swaps required to sort the two sorted subarrays ; Driver Code
temp = [ 0 ] * 100000 NEW_LINE def merge ( A , left , mid , right ) : NEW_LINE INDENT swaps = 0 NEW_LINE i , j , k = left , mid , left NEW_LINE while ( i < mid and j <= right ) : NEW_LINE INDENT if ( A [ i ] <= A [ j ] ) : NEW_LINE INDENT temp [ k ] = A [ i ] NEW_LINE k , i = k + 1 , i + 1 NEW_LINE DEDENT else : NEW_LINE INDENT temp [ k ] = A [ j ] NEW_LINE k , j = k + 1 , j + 1 NEW_LINE swaps += mid - i NEW_LINE DEDENT DEDENT while ( i < mid ) : NEW_LINE INDENT temp [ k ] = A [ i ] NEW_LINE k , i = k + 1 , i + 1 NEW_LINE DEDENT while ( j <= right ) : NEW_LINE INDENT temp [ k ] = A [ j ] NEW_LINE k , j = k + 1 , j + 1 NEW_LINE DEDENT while ( left <= right ) : NEW_LINE INDENT A [ left ] = temp [ left ] NEW_LINE left += 1 NEW_LINE DEDENT return swaps NEW_LINE DEDENT def mergeInsertionSwap ( A , left , right ) : NEW_LINE INDENT swaps = 0 NEW_LINE if ( left < right ) : NEW_LINE INDENT mid = left + ( right - left ) // 2 NEW_LINE swaps += mergeInsertionSwap ( A , left , mid ) NEW_LINE swaps += mergeInsertionSwap ( A , mid + 1 , right ) NEW_LINE swaps += merge ( A , left , mid + 1 , right ) NEW_LINE DEDENT return swaps NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = [ 2 , 1 , 3 , 1 , 2 ] NEW_LINE N = len ( A ) NEW_LINE print ( mergeInsertionSwap ( A , 0 , N - 1 ) ) NEW_LINE DEDENT