text: 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 ; Same as ( l + r ) / 2 , but avoids overflow for large l and h ; Sort first and second halves ; Merge the sorted halves ; Function to print an array ; Driver code
code: #include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE 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 [ n1 ] , R [ n2 ] ; for ( i = 0 ; i < n1 ; i ++ ) L [ i ] = arr [ l + i ] ; for ( j = 0 ; j < n2 ; j ++ ) R [ j ] = arr [ m + 1 + j ] ; i = 0 ; j = 0 ; 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 ) { 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 ) { int i ; for ( i = 0 ; i < size ; i ++ ) printf ( " % d ▁ " , A [ i ] ) ; printf ( " STRNEWLINE " ) ; } int main ( ) { int arr [ ] = { 12 , 11 , 13 , 5 , 6 , 7 } ; int arr_size = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; printf ( " Given ▁ array ▁ is ▁ STRNEWLINE " ) ; printArray ( arr , arr_size ) ; mergeSort ( arr , 0 , arr_size - 1 ) ; printf ( " Sorted array is " printArray ( arr , arr_size ) ; return 0 ; }