Merge Sort | C ++ 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 L [ ] and R [ ] ; Merge the temp arrays Initial indexes of first and second subarrays ; Initial index of merged subarray ; 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 ; Find the middle point ; Sort first and second halves ; Merge the sorted halves ; Function to print an array ; Driver code
#include <iostream> NEW_LINE using namespace std ; void merge ( int arr [ ] , int l , int m , int r ) { int n1 = m - l + 1 ; int n2 = r - m ; int L [ n1 ] , R [ 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 ; int 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 mergeSort ( int arr [ ] , int l , int r ) { if ( l >= r ) { return ; } int m = l + ( r - l ) / 2 ; mergeSort ( arr , l , m ) ; mergeSort ( arr , m + 1 , r ) ; merge ( arr , l , m , r ) ; } void printArray ( int A [ ] , int size ) { for ( int i = 0 ; i < size ; i ++ ) cout << A [ i ] << " ▁ " ; } int main ( ) { int arr [ ] = { 12 , 11 , 13 , 5 , 6 , 7 } ; int arr_size = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << " Given ▁ array ▁ is ▁ STRNEWLINE " ; printArray ( arr , arr_size ) ; mergeSort ( arr , 0 , arr_size - 1 ) ; cout << " Sorted array is " ; printArray ( arr , arr_size ) ; return 0 ; }