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)

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];
    }
}

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];
        }
    }
}

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