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. • 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, ### 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. ### 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= {11, 9, 6, 19, 33, 64, 15, 75, 67, 88};     int i;     int size = sizeof(a)/sizeof(a);    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;    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 88Output array - 6 9 11 15 19 33 64 67 75 88`

• 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)

• Space Complexity sucks !!!
• Space Complexity : O(n), most other algorithm have O(1)  Question 1.Prakash is using Merge sort to sort an array consisting of 2048 elements. After how many passes the array will be completely
sorted?

1. 10
2. 11
3. 9
4. 12

(Cisco, Goldman)

no. of stages = ciel(log2(2048)) = 11

The number of iterations to do so will always be ciel(log2(number of elements))

## 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. 