Merge Sort Program in Python | Java | C | C++

In this article, we will discuss the implementation of merge sort which is another recursive algorithm where we will follow a divide-and-conquer strategy time complexity of merge Sort algorithm is O(N log N) in the worst case.

Merge Sort Program in C 

Solution In C

Code:

#include<stdio.h>
void merge(int arr[],int first,int mid,int last)
{
int n1,n2;
n1=(mid-first+1);
n2=(last-mid);
int Left[n1],Right[n2],i,j,k;

for(i=0;i<n1;i++)
Left[i]=arr[i+first];
for(j=0;j<n2;j++)
Right[j]=arr[mid+j+1];
i=0,j=0,k=first;
while(i<n1 && j<n2){
if(Left[i]<=Right[j])
{
arr[k]=Left[i];
i++;
}
else
{
arr[k]=Right[j];
j++;
}
k++;}
while(i<n1)
    {
        arr[k]=Left[i];
        i++;
        k++;
    }
    while(j<n2)
    {
        arr[k]=Right[j];
        j++;
        k++;
    }
}

void mergesort(int arr[],int first,int last)
{
if(first<last)
{
int mid=first+(last-first)/2;
mergesort(arr,first,mid);
mergesort(arr,mid+1,last);
merge(arr,first,mid,last);
}
}
int main()
{
int size;
    printf("Enter the size of the array:");
    scanf("%d",&size);
    int arr[size],i;
    printf("Enter the element of the array:");
    for(i=0;i<size;i++)
        scanf("%d",&arr[i]);

    printf("Before Sorting Array Element are: ");
    for(i=0;i<size;i++)
        printf("%d ",arr[i]);
mergesort(arr,0,size-1);

printf("\nAfter Sorting Array Element are: ");
        for(i=0;i<size;i++)
        printf("%d ",arr[i]);
}

Input/Output:
Enter the size of the array:5
Enter the element of the array:
4

3
7
8
9
Before Sorting Array Elements are: 4 3 7 8 9
After Sorting Array Elements are: 3 4 7 8 9

Merge sort Program in C plus plus

Solution In C++

Code:

#include<iostream>
using namespace std;
void merge(int arr[],int first,int mid,int last)
{
int n1,n2;
n1=(mid-first+1);
n2=(last-mid);
int Left[n1],Right[n2],i,j,k;

for(i=0;i<n1;i++)
Left[i]=arr[i+first];
for(j=0;j<n2;j++)
Right[j]=arr[mid+j+1];
i=0,j=0,k=first;
while(i<n1 && j<n2){
if(Left[i]<=Right[j])
{
arr[k]=Left[i];
i++;
}
else
{
arr[k]=Right[j];
j++;
}
k++;}
while(i<n1)
    {
        arr[k]=Left[i];
        i++;
        k++;
    }
    while(j<n2)
    {
        arr[k]=Right[j];
        j++;
        k++;
    }
}

void mergesort(int arr[],int first,int last)
{
if(first<last)
{
int mid=first+(last-first)/2;
mergesort(arr,first,mid);
mergesort(arr,mid+1,last);
merge(arr,first,mid,last);
}
}
int main()
{
int size;
    cout<<"Enter the size of the array:";
    cin>>size;
    int arr[size],i;
    cout<<"Enter the element of the array:";
    for(i=0;i<size;i++)
        cin>>arr[i];

    cout<<"Before Sorting Array Element are: ";
    for(i=0;i<size;i++)
        cout<<arr[i]<<" ";

mergesort(arr,0,size-1);

   cout<<"\nAfter Sorting Array Element are: ";
        for(i=0;i<size;i++)
        cout<<arr[i]<<" ";

}

Input/Output:

Enter the size of the array:4
Enter the element of the array:
7
9
3
5
Before Sorting Array Elements are: 7 9 3 5
After Sorting Array Elements are: 5 3 7 9

Merge Sort  Program in Java

Solution In Java

Code:

import java.util.Scanner;
public class Merge_Sort {
static void merge(int arr[],int first,int mid,int last)
{
int n1,n2;
n1=(mid-first+1);
n2=(last-mid);
int Left[]= new int[n1],Right[]=new int[n2],i,j,k;

for(i=0;i<n1;i++)
Left[i]=arr[i+first];
for(j=0;j<n2;j++)
Right[j]=arr[mid+j+1];

k=first;
i=0;
j=0;

while(i<n1 && j<n2){
if(Left[i]<=Right[j])
{
arr[k]=Left[i];
i++;
}
else
{
arr[k]=Right[j];
j++;
}
k++;}
while(i<n1)
    {
        arr[k]=Left[i];
        i++;
        k++;
    }
    while(j<n2)
    {
        arr[k]=Right[j];
        j++;
        k++;
    }
}

static void mergesort(int arr[],int first,int last)
{
if(first<last)
{
int mid=first+(last-first)/2;
mergesort(arr,first,mid);
mergesort(arr,mid+1,last);
merge(arr,first,mid,last);
}
}

public static void main(String[] args) {
Scanner cs=new Scanner(System.in);
int size;
    System.out.print("Enter the size of the array:");
    size=cs.nextInt();
    int arr[]=new int[size],i;
    System.out.print("Enter the element of the array:");
    for(i=0;i<size;i++)
        arr[i]=cs.nextInt();

    System.out.print("Before Sorting Array Element are: ");
    for(i=0;i<size;i++)
        System.out.print(arr[i]+" ");

    mergesort(arr,0,size-1);

        System.out.print("\nAfter Sorting Array Element are: ");
        for(i=0;i<size;i++)
        System.out.print(arr[i]+" ");
cs.close();


}

}

Input/Output:

Enter the size of the array:4
Enter the element of the array:3
2
2
6
Before Sorting Array Elements are: 3 2 2 6 
After Sorting Array Elements are: 2 2 3 6 

Merge Sort Program in python using list

Solution In Python

def merge(arr,first,mid,last):

    n1 = (mid - first + 1)
    n2 = (last - mid)
    Left=[0]*n1
    Right=[0]*n2
    for i in range(n1):
        Left[i] = arr[i + first]
    for j in range(n2):
        Right[j] = arr[mid + j + 1];

    k = first
    i = 0
    j = 0

    while i < n1 and j < n2:
        if Left[i] <= Right[j]:
            arr[k]=Left[i]
            i+=1
        else:
            arr[k]=Right[j]
            j+=1
        k+=1

    while i < n1:
        arr[k] = Left[i]
        i +=1
        k +=1
    while j < n2 :
        arr[k] = Right[j]
        j +=1
        k +=1

def mergesort(arr,first,last):
    if(first<last):
        mid =first + (last - first)// 2
        mergesort(arr, first, mid)
        mergesort(arr, mid + 1, last)
        merge(arr, first, mid, last)

size=int(input("Enter the size of the array:"))
arr=[]
print("Enter the element of the array:")
for i in range(0,size):
    num = int(input())
    arr.append(num)

print("Before Sorting Array Element are: ",arr)

mergesort(arr,0,size-1)

print("\nAfter Sorting Array Element are: ",arr)

Input/Output:

Enter the size of the array:5
Enter the element of the array:
4
3
6
7
4
Before Sorting Array Element are:  [4, 3, 6, 7, 4]

After Sorting Array Element are:  [3, 4, 4, 6, 7]