Count swaps required to sort an array using Insertion Sort | Java program for the above approach ; 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
import java . util . * ; class GFG { static int temp [ ] = new int [ 100000 ] ; static int merge ( int A [ ] , int left , int mid , int right ) { int swaps = 0 ; int i = left , j = mid , k = left ; while ( i < mid && j <= right ) { if ( A [ i ] <= A [ j ] ) { temp [ k ] = A [ i ] ; k ++ ; i ++ ; } else { temp [ k ] = A [ j ] ; k ++ ; j ++ ; swaps += mid - i ; } } while ( i < mid ) { temp [ k ] = A [ i ] ; k ++ ; i ++ ; } while ( j <= right ) { temp [ k ] = A [ j ] ; k ++ ; j ++ ; } while ( left <= right ) { A [ left ] = temp [ left ] ; left ++ ; } return swaps ; } static int mergeInsertionSwap ( int A [ ] , int left , int right ) { int swaps = 0 ; if ( left < right ) { int mid = left + ( right - left ) / 2 ; swaps += mergeInsertionSwap ( A , left , mid ) ; swaps += mergeInsertionSwap ( A , mid + 1 , right ) ; swaps += merge ( A , left , mid + 1 , right ) ; } return swaps ; } public static void main ( String [ ] args ) { int A [ ] = { 2 , 1 , 3 , 1 , 2 } ; int N = A . length ; System . out . println ( mergeInsertionSwap ( A , 0 , N - 1 ) ) ; } }