 AWS Global Infrastructure

### Programming & Frameworks

Topics Covered
• C Programming and Data Structures (41 Blogs)
• Comprehensive Java Course (2 Blogs)
• Java/J2EE and SOA (324 Blogs)
• Spring Framework (8 Blogs)
SEE MORE

# How To Implement Merge Sort in C?

Published on Aug 20,2019 8.8K Views So let us begin

Before we discuss about Merge sort algorithm, let us understand Divide & Conquer technique. In Divide & Conquer algorithm design paradigm, we divide the problems in sub-problems recursively then solve the sub-problems, & at last combine the solutions to find the final result.
One thing to keep in mind while dividing the problems into sub-problems is that, the structure of sub-problems should not change as of the original problem.
Divide & Conquer algorithm has 3 steps:
1. Divide: Breaking the problem into subproblems
2. Conquer: Recursively solving the subproblems
3. Combine: Combining the solutions to get the final result In Merge sort, we divide the array recursively in two halves, until each sub-array contains a single element, and then we merge the sub-array in a way that it results into a sorted array. merge() function merges two sorted sub-arrays into one, wherein it assumes that array[l .. n] and arr[n+1 .. r] are sorted.

Merge sort is one of the efficient & fastest sorting algorithms with the following time complexity:

Worst Case Time Complexity: O(n*log n)
Best Case Time Complexity: O(n*log n)
Average Time Complexity: O(n*log n)

## Merge Sort Algorithm

MergeSort(arr[], l, r), where l is the index of the first element & r is the index of the last element.
If r > l
1. Find the middle index of the array to divide it in two halves:
m = (l+r)/2
2. Call MergeSort for first half:
mergeSort(array, l, m)
3. Call mergeSort for second half:
mergeSort(array, m+1, r)
4. Recursively, merge the two halves in a sorted manner, so that only one sorted array is left:
merge(array, l, m, r)

Example:

1. Divide the unsorted array recursively until 1 element in each sub-array remains. 2. Recursively, merge sub-arrays to produce sorted sub-arrays until all the sub-array merges and only one array remains. To sort an array using Merge sort, following is the process
We take two variables p & r where p stores the staring index & stores the last index of the array
Next, we find the mid of the array to break it in two halves. Formula yo do so is (p+r)/2 and mark the middle element as m.
Next step is to break the given array into two subarrays from the middle element, i.e. from index p to m & m+1 to r.
We continue to break the subarrays until we reach to a level where each sub array contains 1 element.
Next we merge the sub-array recursively in a sorted order, so that we finally get a sorted array.

## Merge Sort Function in C

```void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Finding mid element
int m = l+(r-l)/2;
// Recursively sorting both the halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);

// Merge the array
merge(arr, l, m, r);
}
}
```

## Merge Function in C

```void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// Create temp arrays
int L[n1], R[n2];
// Copy data to temp array
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
// Merge the temp arrays
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L[]
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[]
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
```

## Merge Sort C Program

```#include<stdlib.h>
#include<stdio.h>
// Merge Function
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
```

### // Merge Sort Function in C

```void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
int m = l+(r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
```

### // Functions to Print Elements of Array

```void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("n");
}
```

### // Main Method

```int main()
{
int arr[] = {85, 24, 63, 45, 17, 31, 96, 50};
int arr_size = sizeof(arr)/sizeof(arr);
printf("Given array is n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("nSorted array is n");
printArray(arr, arr_size);
return 0;
}
```

Output: Now after executing the above C program you would have understood how Merge Sort works & how to implement it in C. I hope this blog is informative and added value to you.

With this we come to the end of this blog on ‘Merge Sort In C’. I hope you found this informative and helpful, stay tuned for more tutorials on similar topics.

You may also checkout our training program to get in-depth knowledge on jQuery along with its various applications, you can enroll here for live online training with 24/7 support and lifetime access.Implement the above code with different strings and modifications. Now, we have a good understanding of all key concepts related to the pointer.

Got a question for us? Mention them in the comments section of  this blog and we will get back to you. REGISTER FOR FREE WEBINAR Thank you for registering Join Edureka Meetup community for 100+ Free Webinars each month