# Merge Sort program in the data structure

Views 105

### About:

Below we have a C program implementing merge sort algorithm.

### Program:

```/*
a[] is the array, p is starting index, that is 0,
and r is the last index of array.
*/

#include <stdio.h>

// lets take a[5] = {32, 45, 67, 2, 7} as the array to be sorted.

// merge sort function
void mergeSort(int a[], int p, int r)
{
int q;
if(p < r)
{
q = (p + r) / 2;
mergeSort(a, p, q);
mergeSort(a, q+1, r);
merge(a, p, q, r);
}
}

// function to merge the subarrays
void merge(int a[], int p, int q, int r)
{
int b[5];   //same size of a[]
int i, j, k;
k = 0;
i = p;
j = q + 1;
while(i <= q && j <= r)
{
if(a[i] < a[j])
{
b[k++] = a[i++];    // same as b[k]=a[i]; k++; i++;
}
else
{
b[k++] = a[j++];
}
}

while(i <= q)
{
b[k++] = a[i++];
}

while(j <= r)
{
b[k++] = a[j++];
}

for(i=r; i >= p; i--)
{
a[i] = b[--k];  // copying back the sorted list to a[]
}
}

// function to print the array
void printArray(int a[], int size)
{
int i;
for (i=0; i < size; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}

int main()
{
int arr[] = {32, 45, 67, 2, 7};
int len = sizeof(arr)/sizeof(arr[0]);

printf("Given array: \n");
printArray(arr, len);

// calling merge sort
mergeSort(arr, 0, len - 1);

printf("\nSorted array: \n");
printArray(arr, len);
return 0;
} ```

### Output:

```Output : Given array:
32 45 67 2 7
Sorted array:
2 7 32 45 67```

### Explanation:

Merge Sort follows the rule of Divide and Conquer to sort a given set of numbers/elements, recursively, hence consuming less time.

In the last two tutorials, we learned about Selection Sort and Insertion Sort, both of which have a worst-case running time of `O(n2)`. As the size of input grows, insertion and selection sort can take a long time to run.

Merge sort , on the other hand, runs in `O(n*log n)` time in all the cases.

Before jumping on to, how merge sort works and it's implementation, first lets understand what is the rule of Divide and Conquer?

#### Share Me:

Data Structure Programming Lists