Please login

Prime

Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime

Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock

Merge Sort in C

How Merge Sort Works inC

Merge Sort is an example of the divide and conquer approach.It divides the array into equal halves and  then combine in a sorted manner.In merge sort the unsorted list is  divided into N sub lists, each having one element.

Merge sort Divide and Conquer
  • The complexity of the merge sort algorithm is O(NlogN) where N is the number of elements to sort.
  • It can be applied  to file of any sizes.
  • In Merge sort all the elements are divided into two sub-array again and again until one element is left.
  • After the completion of the divide and conquer the elements are merged to make a sorted array .
  • This sorting is less efficient and it require more space as compare to other sorting,
Merge Sort Working in C Intro

Execution of Merge sort

This is unsorted array and it will make a sorted array by using merge sort algorithm in this array it will be use divide technique .

first of all the array will be divide in to  N sub array.  and the  array divide until each having only one element.

In this array each element should be divide each other.the sorted element will be merge by using conquer technique.  and the last all element will be merged.

And the finally array or list is sorted by using merge sort algorithm. 

Merge Sort in C Example

Code of Merge Sort in C

#include <stdio.h>

void mergeSort(int[],int,int);
void merge(int[],int,int,int);

void display(int arr[], int size){
int i;
for(i = 0; i < size; i++){
printf("%d ",arr[i]);
}
printf("\n");
}

void main()
{
int a[10]= {11, 9, 6, 19, 33, 64, 15, 75, 67, 88};
int i;

int size = sizeof(a)/sizeof(a[0]);
display(a, size);

mergeSort(a,0,size-1);
display(a, size);
}

void mergeSort(int a[], int strt, int end)
{
int mid;
if(strt<end)
{
mid = (strt+end)/2;

mergeSort(a,strt,mid);
mergeSort(a,mid+1,end);
merge(a,strt,mid,end);
}
}

void merge(int a[], int strt, int mid, int end)
{
int i=strt,j=mid+1,p,index = strt;
int temp[10];

while(i<=mid && j<=end)
{
if(a[i]<a[j])
{
temp[index] = a[i];
i = i+1;
}
else
{
temp[index] = a[j];
j = j+1;
}

index++;
}
if(i>mid)
{
while(j<=end)
{
temp[index] = a[j];
index++;
j++;
}
}
else
{
while(i<=mid)
{
temp[index] = a[i];
index++;
i++;
}
}
p = strt;
while(p<index)
{
a[p]=temp[p];
p++;
}
}

Output

Input array - 11 9 6 19 33 64 15 75 67 88
Output array - 6 9 11 15 19 33 64 67 75 88

Merge Sort Advantages

  • Fast ! Time complexity : O(N Log N)
  • Reliable, it gives same time complexity in all cases.
  • Tim sort variant of this really powerful (Not important for Placements)

Merge Sort Disadvantages

  • Space Complexity sucks !!!
  • Space Complexity : O(n), most other algorithm have O(1)
Merge Sort in C meme

Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.

Data Structures and Algorithm Learn Sorting