Merge Sort | Java program for Merge Sort ; Merges two subarrays of arr [ ] . First subarray is arr [ l . . m ] Second subarray is arr [ m + 1. . r ] ; Find sizes of two subarrays to be merged ; Create temp arrays ; Copy data to temp arrays ; Merge the temp arrays Initial indexes of first and second subarrays ; Initial index of merged subarry array ; Copy remaining elements of L [ ] if any ; Copy remaining elements of R [ ] if any ; Main function that sorts arr [ l . . r ] using merge ( ) ; Find the middle point ; Sort first and second halves ; Merge the sorted halves ; A utility function to print array of size n ; Driver code
class MergeSort { void merge ( int arr [ ] , int l , int m , int r ) { int n1 = m - l + 1 ; int n2 = r - m ; int L [ ] = new int [ n1 ] ; int R [ ] = new int [ n2 ] ; for ( int i = 0 ; i < n1 ; ++ i ) L [ i ] = arr [ l + i ] ; for ( int j = 0 ; j < n2 ; ++ j ) R [ j ] = arr [ m + 1 + j ] ; int i = 0 , j = 0 ; int k = l ; while ( i < n1 && j < n2 ) { if ( L [ i ] <= R [ j ] ) { arr [ k ] = L [ i ] ; i ++ ; } else { arr [ k ] = R [ j ] ; j ++ ; } k ++ ; } while ( i < n1 ) { arr [ k ] = L [ i ] ; i ++ ; k ++ ; } while ( j < n2 ) { arr [ k ] = R [ j ] ; j ++ ; k ++ ; } } void sort ( int arr [ ] , int l , int r ) { if ( l < r ) { int m = l + ( r - l ) / 2 ; sort ( arr , l , m ) ; sort ( arr , m + 1 , r ) ; merge ( arr , l , m , r ) ; } } static void printArray ( int arr [ ] ) { int n = arr . length ; for ( int i = 0 ; i < n ; ++ i ) System . out . print ( arr [ i ] + " ▁ " ) ; System . out . println ( ) ; } public static void main ( String args [ ] ) { int arr [ ] = { 12 , 11 , 13 , 5 , 6 , 7 } ; System . out . println ( " Given ▁ Array " ) ; printArray ( arr ) ; MergeSort ob = new MergeSort ( ) ; ob . sort ( arr , 0 , arr . length - 1 ) ; System . out . println ( " Sorted array "); printArray ( arr ) ; } }