C Menu
- Basics of C
- Basics of C Programming
- Features of C Programming
- Preprocessors in C Programming
- History of C Programming
- Low Level Programming
- Why C is Middle Level Language
- Introduction to C programming
- Structure of a C program
- Input-Output Functions
- Difference between Compiler and Interpreter
- Assembler v/s Compiler v/s Interpreter v/s Linker v/s Loader
- Basics to Code
- Operators in C
- Operators in C
- Precedence Associativity Operators
- Arithmetic Operators
- Relational Operators
- Logical Operators
- Bitwise Operators
- Assignment Operators
- Ternary Operators in C
- Size of Operators
- Conditional Operators
- Comma Operators
- Format Specifiers in C
- Difference between %d and %i
- Difference between %f, %e, %E and %g
- How to print% using printf
- How to print \ using printf
- How to print “” using printf
- What is the use of %p in C
- Library Functions in C
- pow() in C
- sqrt() in C
- Storage Classes in C
- Conditional statements and Decision Making in C
- DataType & Functions in C
- Arrays, String, Structure, Union and Enum
- Pointer in C
- Library Function in C
- Library function in C
- math.h in c
- Library function math.h acos
- Library function math.h acosh
- Library function math.h asin
- Library function math.h asinh
- Library function math.h atan
- Library function math.h atan2
- Library function math.h atanh
- Library function math.h cbrt
- Library function math.h cell
- Library function math.h cos
- Library function math.h cosh
- Library function math.h exp
- Library function math.h fabs
- Library function math.h floor
- Library function math.h hypot
- Library function math.h log
- Library function math.h log10
- Library function math.h pow
- Library function math.h sin
- Library function math.h sinh
- Library function math.h sqrt
- Library function math.h tan
- Library function math.h tanh
- Library function studio.h clearerr
- Library function string.h strcat
- Library function string.h strcmp
- Library function string.h strcpy
- Library function string.h strlen
- File Handling
- Dynamic Memory Allocation
- Miscellaneous Topics in C
- Miscellaneous Coding Questions
PREPINSTA PRIME
Merge 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