Implementation of Merge Sort using C in dataStructure developerIndian.com

Updated: 13/08/2023 by Computer Hope

Here we are seeing how we can implement Merge Sort in c , how to implement merge sort and creating subfunction using c

A Sorting Algorithm is used to make a given array or list or objects or elements according to a comparison operator on the give input . The operator is decide the new order of element in the formate of data structure like array , list , Object etc

we see that Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves and calls itself for the two halves, and then it merges the two sorted halves. The merge() function is used for merging two halves. The function merge(arr, l, m, r) is a key process that suppose that arr[l....m] and arr[m+1....r] are sorted and merges the two sorted sub-arrays into one. See the following details.

      
      
#include<stdio.h>
#define MAX 50

void mergeSort(int arr[],int low,int mid,int high);
void partition(int arr[],int low,int high);

int main(){
   
    int merge[MAX],i,n;

    printf("Enter the total number of elements: ");
    scanf("%d",&n);

    printf("Enter the elements which to be sort: ");
    for(i=0;i<n;i++){
         scanf("%d",&merge[i]);
    }

    partition(merge,0,n-1);

    printf("After merge sorting elements are: ");
    for(i=0;i<n;i++){
         printf("%d ",merge[i]);
    }

   return 0;
}

void partition(int arr[],int low,int high){

    int mid;

    if(low<high){
         mid=(low+high)/2;
         partition(arr,low,mid);
         partition(arr,mid+1,high);
         mergeSort(arr,low,mid,high);
    }
}

void mergeSort(int arr[],int low,int mid,int high){

    int i,m,k,l,temp[MAX];

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high)){

         if(arr[l]<=arr[m]){
             temp[i]=arr[l];
             l++;
         }
         else{
             temp[i]=arr[m];
             m++;
         }
         i++;
    }

    if(l>mid){
         for(k=m;k<=high;k++){
             temp[i]=arr[k];
             i++;
         }
    }
    else{
         for(k=l;k<=mid;k++){
             temp[i]=arr[k];
             i++;
         }
    }
   
    for(k=low;k<=high;k++){
         arr[k]=temp[k];
    }
}


     
    

Here you can able to see merge sort algorithm in Java Language

     
     class MergeSort
{
  void merge(int Arr[], int lt, int mid, int rt)
  {
    int L1 = mid - lt + 1;
    int L2 = rt - mid;
    int left[] = new int[L1];
    int right[] = new int[L2];
    for (int i = 0; i < L1; i++)
      left[i] = Arr[lt + i];
    for (int j = 0; j < L2; j++)
      right[j] = Arr[mid + 1 + j];
    int i = 0, j = 0;
    int k = l;
    while (i < L1 && j < L2) {
      if (left[i] <= right[j]) {
        Arr[k] = left[i];
        i++;
      }
      else {
        Arr[k] = right[j];
        j++;
      }
      k++;
    }
    while (i < L1) 
      Arr[k++] = left[i++];
  
    while (j < L2) 
      Arr[k++] = right[j++];
  }
  void Merge_sort(int Arr[], int l, int r)
  {
    if (l < r) {
      int mid =l+ (r-l)/2;
      Merge_sort(Arr, l, mid);
      Merge_sort(Arr, mid + 1, r);
      merge(Arr, l, mid, r);
    }
  }
  static void Display_array(int a[])
  {
    int n = a.length;
    for (int i = 0; i < n; ++i)
      System.out.print(a[i] + " ");
    System.out.println();
  }
  public static void main(String args[])
  {
    int array[] = {1,6,3,2,7,5,8,4};
    System.out.println("Given array is: ");
    Display_array(array);
    MergeSort ob = new MergeSort();
    ob.Merge_sort(array, 0, array.length - 1);
    System.out.println("\nSorted array is: ");
    Display_array(array);
  }
}
    
     

Here you can able to see merge sort algorithm in Python Language

  
  def Merge_sort(Arr):
  if len(Arr) > 1:
    mid = len(Arr)//2
    left = Arr[:mid]
    right = Arr[mid:]
    Merge_sort(left)
    Merge_sort(right)
    i = j = k = 0
    while i < len(left) and j < len(right):
      if len[i] < right[j]:
        Arr[k] = left[i]
        i += 1
      else:
        Arr[k] = right[j]
        j += 1
      k += 1
    while i < len(left):
      Arr[k] = left[i]
      i += 1
      k += 1
    while j < len(right):
      Arr[k] = right[j]
      j += 1
      k += 1
def Display_list(a):
  for i in range(len(a)):
    print(a[i], end=" ")
  print()
if __name__ == '__main__':
  list = [1,6,3,2,7,5,8,4]
  print("Given array is: ", end="\n")
  Display_list(list)
  Merge_sort(list)
  print("Sorted array is: ", end="\n")
  Display_list(list)