Counting cross lines in an array | Java program to count cross line in array ; Merges two subarrays of arr [ ] . First subarray is arr [ l . . m ] Second subarray is arr [ m + 1. . r ] ; create temp arrays ; Copy data to temp arrays L [ ] and R [ ] ; i = 0 ; Initial index of first subarray j = 0 ; Initial index of second subarray k = l ; Initial index of merged subarray ; == == == == == == == == == == == == == == == == == == == == == = MAIN PORTION OF CODE == == == == == == == == == == == == == == == == == == == == = add all line which is cross by current element ; Copy the remaining elements of L [ ] , if there are any ; Copy the remaining elements of R [ ] , if there are any ; l is for left index and r is right index of the sub - array of arr to be sorted ; Same as ( l + r ) / 2 , but avoids overflow for large l and h ; Sort first and second halves ; function return count of cross line in an array ; Driver Code
import java . util . * ; class GFG { static int count_crossline ; static void merge ( int arr [ ] , int l , int m , int r ) { int i , j , k ; int n1 = m - l + 1 ; int n2 = r - m ; int [ ] L = new int [ n1 ] ; int [ ] R = new int [ n2 ] ; for ( i = 0 ; i < n1 ; i ++ ) { L [ i ] = arr [ l + i ] ; } for ( j = 0 ; j < n2 ; j ++ ) { R [ j ] = arr [ m + 1 + j ] ; } while ( i < n1 && j < n2 ) { if ( L [ i ] <= R [ j ] ) { arr [ k ] = L [ i ] ; i ++ ; } else { arr [ k ] = R [ j ] ; count_crossline += ( n1 - i ) ; j ++ ; } k ++ ; } while ( i < n1 ) { arr [ k ] = L [ i ] ; i ++ ; k ++ ; } while ( j < n2 ) { arr [ k ] = R [ j ] ; j ++ ; k ++ ; } } static void mergeSort ( int arr [ ] , int l , int r ) { if ( l < r ) { int m = l + ( r - l ) / 2 ; mergeSort ( arr , l , m ) ; mergeSort ( arr , m + 1 , r ) ; merge ( arr , l , m , r ) ; } } static int countCrossLine ( int arr [ ] , int n ) { mergeSort ( arr , 0 , n - 1 ) ; return count_crossline ; } public static void main ( String [ ] args ) { int arr [ ] = { 12 , 11 , 13 , 5 , 6 , 7 } ; int n = arr . length ; System . out . println ( countCrossLine ( arr , n ) ) ; } }