Description
* Merge sort is a algorithm that uses the divide, conquer and combine algorithm.
* Steps of merge sort
1) Partition the n-element array into two sub-arrays of n/2 elements.
2) Sort two sub-arrays recursively using merge sort.
3) Merge the two sorted sub-arrays of size n/2 to produce the sorted array of
n elements.
* If the array is of length 0 or 1, then it is already sorted.
* Time complexity of merge sort in average, best and worst case : O(nlogn)
* Space complexity : O(n)
* Merge sort is a algorithm that uses the divide, conquer and combine algorithm.
* Steps of merge sort
1) Partition the n-element array into two sub-arrays of n/2 elements.
2) Sort two sub-arrays recursively using merge sort.
3) Merge the two sorted sub-arrays of size n/2 to produce the sorted array of
n elements.
* If the array is of length 0 or 1, then it is already sorted.
* Time complexity of merge sort in average, best and worst case : O(nlogn)
* Space complexity : O(n)
* Merge sort is a algorithm that uses the divide, conquer and combine algorithm. * Steps of merge sort 1) Partition the n-element array into two sub-arrays of n/2 elements. 2) Sort two sub-arrays recursively using merge sort. 3) Merge the two sorted sub-arrays of size n/2 to produce the sorted array of n elements. * If the array is of length 0 or 1, then it is already sorted. * Time complexity of merge sort in average, best and worst case : O(nlogn) * Space complexity : O(n)
C/C++
/* C program of merge sort */
//Save it as MergeSort.c
#include<stdio.h>
int main()
{
int i,n;
printf("Enter the size of array : ");
scanf("%d",&n);
int arr[n];
printf("\nEnter element : ");
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
//Call a function of merge sort
merge_sort(arr,0,n-1);
//Array after sorting
printf("\nThe Sorted array is : ");
for(i=0;i<n;i++)
{
printf("%d ",arr[i]);
}
return 0;
}
void merge_sort(int arr[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
merge(arr,low,mid,high);
}
}
void merge(int arr[],int beg,int mid,int end)
{
int i=beg,j=mid+1,index=beg,temp[100],k;
while((i<=mid) && (j<=end))
{
if(arr[i]<arr[j])
{
temp[index]=arr[i];
i++;
}
else
{
temp[index]=arr[j];
j++;
}
index++;
}
if(i>mid)
{
while(j<=end)
{
temp[index]=arr[j];
j++;
index++;
}
}
else
{
while(i<=mid)
{
temp[index]=arr[i];
i++;
index++;
}
}
for(k=beg;k<index;k++)
{
arr[k]=temp[k];
}
}
/* C program of merge sort */
//Save it as MergeSort.c
#include<stdio.h>
int main()
{
int i,n;
printf("Enter the size of array : ");
scanf("%d",&n);
int arr[n];
printf("\nEnter element : ");
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
//Call a function of merge sort
merge_sort(arr,0,n-1);
//Array after sorting
printf("\nThe Sorted array is : ");
for(i=0;i<n;i++)
{
printf("%d ",arr[i]);
}
return 0;
}
void merge_sort(int arr[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
merge(arr,low,mid,high);
}
}
void merge(int arr[],int beg,int mid,int end)
{
int i=beg,j=mid+1,index=beg,temp[100],k;
while((i<=mid) && (j<=end))
{
if(arr[i]<arr[j])
{
temp[index]=arr[i];
i++;
}
else
{
temp[index]=arr[j];
j++;
}
index++;
}
if(i>mid)
{
while(j<=end)
{
temp[index]=arr[j];
j++;
index++;
}
}
else
{
while(i<=mid)
{
temp[index]=arr[i];
i++;
index++;
}
}
for(k=beg;k<index;k++)
{
arr[k]=temp[k];
}
}
/* C program of merge sort */ //Save it as MergeSort.c #include<stdio.h> int main() { int i,n; printf("Enter the size of array : "); scanf("%d",&n); int arr[n]; printf("\nEnter element : "); for(i=0;i<n;i++) { scanf("%d",&arr[i]); } //Call a function of merge sort merge_sort(arr,0,n-1); //Array after sorting printf("\nThe Sorted array is : "); for(i=0;i<n;i++) { printf("%d ",arr[i]); } return 0; } void merge_sort(int arr[],int low,int high) { int mid; if(low<high) { mid=(low+high)/2; merge_sort(arr,low,mid); merge_sort(arr,mid+1,high); merge(arr,low,mid,high); } } void merge(int arr[],int beg,int mid,int end) { int i=beg,j=mid+1,index=beg,temp[100],k; while((i<=mid) && (j<=end)) { if(arr[i]<arr[j]) { temp[index]=arr[i]; i++; } else { temp[index]=arr[j]; j++; } index++; } if(i>mid) { while(j<=end) { temp[index]=arr[j]; j++; index++; } } else { while(i<=mid) { temp[index]=arr[i]; i++; index++; } } for(k=beg;k<index;k++) { arr[k]=temp[k]; } }
Input:
Enter the size of array : 9
Enter element : 15
5
24
8
1
3
16
10
20
Output:
The Sorted array is : 1 3 5 8 10 15 16 20 24
Input:
Enter the size of array : 9
Enter element : 15
5
24
8
1
3
16
10
20
Output:
The Sorted array is : 1 3 5 8 10 15 16 20 24
Input: Enter the size of array : 9 Enter element : 15 5 24 8 1 3 16 10 20 Output: The Sorted array is : 1 3 5 8 10 15 16 20 24
Java
/* Java program of merge sort */
//Save it as MergeSort.java
import java.io.*;
import java.util.Scanner;
public class MergeSort {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int i,n;
System.out.println("Enter the size of array : ");
n = scanner.nextInt();
int arr[] = new int[n];
System.out.println("Enter element : ");
for(i=0;i<n;i++)
{
arr[i] = scanner.nextInt();
}
//Call a function of merge sort
merge_sort(arr,0,n-1);
//Array after sorting
System.out.println("\nThe Sorted array is : ");
for(i=0;i<n;i++)
{
System.out.print(arr[i]+ " ");
}
}
public static void merge_sort(int arr[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
merge(arr,low,mid,high);
}
}
public static void merge(int arr[],int beg,int mid,int end)
{
int i=beg, j=mid+1, index=beg, k;
int temp[] = new int[100];
while((i<=mid) && (j<=end))
{
if(arr[i]<arr[j])
{
temp[index]=arr[i];
i++;
}
else
{
temp[index]=arr[j];
j++;
}
index++;
}
if(i>mid)
{
while(j<=end)
{
temp[index]=arr[j];
j++;
index++;
}
}
else
{
while(i<=mid)
{
temp[index]=arr[i];
i++;
index++;
}
}
for(k=beg;k<index;k++)
{
arr[k]=temp[k];
}
}
}
/* Java program of merge sort */
//Save it as MergeSort.java
import java.io.*;
import java.util.Scanner;
public class MergeSort {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int i,n;
System.out.println("Enter the size of array : ");
n = scanner.nextInt();
int arr[] = new int[n];
System.out.println("Enter element : ");
for(i=0;i<n;i++)
{
arr[i] = scanner.nextInt();
}
//Call a function of merge sort
merge_sort(arr,0,n-1);
//Array after sorting
System.out.println("\nThe Sorted array is : ");
for(i=0;i<n;i++)
{
System.out.print(arr[i]+ " ");
}
}
public static void merge_sort(int arr[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
merge(arr,low,mid,high);
}
}
public static void merge(int arr[],int beg,int mid,int end)
{
int i=beg, j=mid+1, index=beg, k;
int temp[] = new int[100];
while((i<=mid) && (j<=end))
{
if(arr[i]<arr[j])
{
temp[index]=arr[i];
i++;
}
else
{
temp[index]=arr[j];
j++;
}
index++;
}
if(i>mid)
{
while(j<=end)
{
temp[index]=arr[j];
j++;
index++;
}
}
else
{
while(i<=mid)
{
temp[index]=arr[i];
i++;
index++;
}
}
for(k=beg;k<index;k++)
{
arr[k]=temp[k];
}
}
}
/* Java program of merge sort */ //Save it as MergeSort.java import java.io.*; import java.util.Scanner; public class MergeSort { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int i,n; System.out.println("Enter the size of array : "); n = scanner.nextInt(); int arr[] = new int[n]; System.out.println("Enter element : "); for(i=0;i<n;i++) { arr[i] = scanner.nextInt(); } //Call a function of merge sort merge_sort(arr,0,n-1); //Array after sorting System.out.println("\nThe Sorted array is : "); for(i=0;i<n;i++) { System.out.print(arr[i]+ " "); } } public static void merge_sort(int arr[],int low,int high) { int mid; if(low<high) { mid=(low+high)/2; merge_sort(arr,low,mid); merge_sort(arr,mid+1,high); merge(arr,low,mid,high); } } public static void merge(int arr[],int beg,int mid,int end) { int i=beg, j=mid+1, index=beg, k; int temp[] = new int[100]; while((i<=mid) && (j<=end)) { if(arr[i]<arr[j]) { temp[index]=arr[i]; i++; } else { temp[index]=arr[j]; j++; } index++; } if(i>mid) { while(j<=end) { temp[index]=arr[j]; j++; index++; } } else { while(i<=mid) { temp[index]=arr[i]; i++; index++; } } for(k=beg;k<index;k++) { arr[k]=temp[k]; } } }
Input:
Enter the size of array :
9
Enter element :
15
5
24
8
1
3
16
10
20
Output:
The Sorted array is :
1 3 5 8 10 15 16 20 24
Input:
Enter the size of array :
9
Enter element :
15
5
24
8
1
3
16
10
20
Output:
The Sorted array is :
1 3 5 8 10 15 16 20 24
Input: Enter the size of array : 9 Enter element : 15 5 24 8 1 3 16 10 20 Output: The Sorted array is : 1 3 5 8 10 15 16 20 24
Related programs
1) Selection Sort2) Bubble Sort
3) Insertion Sort
4) Quick Sort