Programming
Aptitude
Syllabus
Interview Preparation
Interview Exp.
Off Campus
0Merge Sort in C
How Merge Sort Works in C
Merge Sort is an example of the divide and conquer approach. It divides the array into equal halves and then combines in a sorted manner. In merge sort the unsorted list is divided into N sub-lists, each having one element.
| Time Complexity | Θ(n Log n) |
| Best Case | Ω(n Log n) |
| Worst Case | O(n Log n) |
| Space Complexity | O(n) |
Execution of Merge sort Program in C
Dividing
For an unsorted array and we will make a sorted array by using the merge sort algorithm in this array will be used divide and conquer technique.
First of all the array will be divided into N sub-arrays that is the array divided until each has only one element.
Conquering/Merging
The N sub-Arrays will then be merged one by one. Make sure that at each merging step the subarray becomes sorted (see image below). This part of the algorithm is called a conquering/merging.
The sub-arrays are merged in sorted fashion one by one till the resultant is the size of the actual array.
Program for Merge Sort
- Method 1 – Two temporary subarrays
- Method 2 – One Temporary subarray
Both will have the space complexity of O(N) as the combined size of two temporary arrays in method 1 will be the same as single temporary array used in method 2.
- Space Complexity : O(n)
- Time Complexity : O(n log n)
#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]);
printf("Input: ");
display(a, size);
mergeSort(a, 0, size-1);
printf("Output: ");
display(a, size);
}
void mergeSort(int a[], int left, int right)
{
int mid;
if(left < right)
{
// can also use mid = left + (right - left) / 2
// this can avoid data type overflow
mid = (left + right)/2;
// recursive calls to sort first half and second half subarrays
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
merge(a, left, mid, right);
}
}
void merge(int a[], int left, int mid, int right)
{
int i = left, j = mid + 1, p, index = left;
int temp[10];
while(i<=mid && j<=right)
{
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 <= right)
{
temp[index] = a[j];
index++;
j++;
}
}
else
{
while(i <= mid)
{
temp[index] = a[i];
index++;
i++;
}
}
p = left;
while(p < index)
{
a[p]=temp[p];
p++;
}
}
Output
Input: 11 9 6 19 33 64 15 75 67 88 Output: 6 9 11 15 19 33 64 67 75 88
- Space Complexity : O(n)
- Time Complexity : O(n log n)
This method also has same space complexity as even though there are two temporary arrays created in previous approach. The combined size of still n in previous case and here also we have created even though one array but of size n.
#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]);
printf("Input: ");
display(a, size);
mergeSort(a, 0, size-1);
printf("Output: ");
display(a, size);
}
void mergeSort(int a[], int left, int right)
{
int mid;
if(left < right)
{
// can also use mid = left + (right - left) / 2
// this can avoid data type overflow
mid = (left + right)/2;
// recursive calls to sort first half and second half subarrays
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
merge(a, left, mid, right);
}
}
void merge(int arr[], int left, int mid, int right)
{
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
// create temp arrays to store left and right subarrays
int L[n1], R[n2];
// Copying data to temp arrays L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// here we merge the temp arrays back into arr[l..r]
i = 0; // Starting index of L[i]
j = 0; // Starting index of R[i]
k = left; // Starting index of merged subarray
while (i < n1 && j < n2)
{
// place the smaller item at arr[k] pos
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L[], if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[], if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}Output
Input: 11 9 6 19 33 64 15 75 67 88 Output: 6 9 11 15 19 33 64 67 75 88
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Quick Facts about Merge Sort
- 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 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)
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
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?
- 10
- 11
- 9
- 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.
Login/Signup to comment