Merge Sort in C

By | May 3, 2020
Merge Sort in C

Merge Sort in C is a sorting algorithm. When you have a large data collection that is not arranged and it requires you to search a particular data set in the collection then a sorting technique is used to arrange large data in a sequence. Sorting reduces the time of data searching in large data collection. There are several sorting algorithms are available to apply according to the need of the user.

Merge Sort in C

Here we start with the understanding of basics merge sort in c.

Vamware

What is Merge Sort?

Like Quick sort, Merge sort is also based on the divide and conquer technique. It repeatedly divides a list into sub-lists until each sub-list has only one element and then merges them in a way to get a sorted list at the end.

As the list can be divided in the max of logN parts and then merging of all sub-lists into a sorted list takes O(N) time so the worst-case running this algorithm is O(N logN)

Let’s understand this with an example to get a better knowledge of merge sort.

Merge Sort

This is an example where we have a list of 6 elements. To find the mid element to divide the list- mid= (0+5)/2, n is the position of the last element. Below we can see that in the first step, the list is divided into 2 sub-lists. We have a list containing (9, 7, 8, 3, 2, 1). First divided into 2 lists that are (9, 7, 8) and (3, 2, 1). These lists of size 3 are then divided into again 2 sub-lists of each that is (9, 7) and (8), and (3, 2) and (1). This process will go until we get each sub-lists having single elements. So now we have (9), (7), (8), (3), (2), (1).

No further breakdown is possible now. Now 2 sub-lists formed in the last step to be merged in sorted order by comparing them elements. Like 9 and 7 are compared and 7 will be placed before 9. The same applied to others also. And finally, we will get the sorted array as 1, 2, 3, 7, 8, 9.

Example of Merge Sort using C Programming

#include<stdlib.h> 
#include<stdio.h> 
// Merges two subarrays of arr[]. 
// 1st subarray is arr[l..m] 
// 2nd subarray is arr[m+1..r] 
void merge(int arr[], int l, int m, int r) 
{ 
int i, j, k; 
int n1 = m - l + 1; 
int n2 = r - m; 
/* To create temp arrays */
int L[n1], R[n2]; 
/* This will copy data to temp arrays L[] and R[] */
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 back into arr[l..r]*/
i = 0; // starting index of first subarray 
j = 0; // starting index of second subarray 
k = l; // starting index of merged subarray 
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[], if there is any */
while (i < n1) 
{ 
arr[k] = L[i]; 
i++; 
k++; 
} 
/* Copy the remaining elements of R[], if there is any */
while (j < n2) 
{ 
arr[k] = R[j]; 
j++; 
k++; 
} 
} 
/* l meant for left index and r is right index of the 
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r) 
{ 
if (l < r) 
{ 
// Same as (l+r)/2, but avoids overflow for 
// large l and h 
int m = l+(r-l)/2; 
// Sort first and second halves 
mergeSort(arr, l, m); 
mergeSort(arr, m+1, r); 
merge(arr, l, m, r); 
} 
} 
/* Function to print an array */
void printArray(int A[], int size) 
{ 
int i; 
for (i=0; i < size; i++) 
printf("%d ", A[i]); 
printf("\n"); 
} 
/* This program to test above functions */
int main() 
{ 
int arr[] = {21, 11, 43, 5, 19, 7}; 
int arr_size = sizeof(arr)/sizeof(arr[0]); 
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:

Given array is
21 11 43 5 19 7
Sorted array is
5 7 11 21 19 43

Example of Merge Sort using Java

class MergeSort 
{ 
// Merges two subarrays of arr[]. 
// First subarray is arr[l..m] 
// Second subarray is arr[m+1..r] 
void merge(int arr[], int l, int m, int r) 
{ 
// To check the sizes of two subarrays to be merged 
int n1 = m - l + 1; 
int n2 = r - m; 
/* Create temp arrays */
int L[] = new int [n1]; 
int R[] = new int [n2]; 
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i) 
L[i] = arr[l + i]; 
for (int j=0; j<n2; ++j) 
R[j] = arr[m + 1+ j]; 
/* Merge the temp arrays */
// starting indexes of first and second subarrays 
int i = 0, j = 0; 
// starting index of merged subarry array 
int 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 remaining elements of L[] if any */
while (i < n1) 
{ 
arr[k] = L[i]; 
i++; 
k++; 
} 
/* Copy remaining elements of R[] if any */
while (j < n2) 
{ 
arr[k] = R[j]; 
j++; 
k++; 
} 
} 
// Main function for sorting arr[l..r] using 
// merge() 
void sort(int arr[], int l, int r) 
{ 
if (l < r) 
{ 
// Find the middle point 
int m = (l+r)/2; 
// Sort first and second halves 
sort(arr, l, m); 
sort(arr , m+1, r); 
// Merge the sorted halves 
merge(arr, l, m, r); 
} 
} 
/* Function to print array of size n */
static void printArray(int arr[]) 
{ 
int n = arr.length; 
for (int i=0; i<n; ++i) 
System.out.print(arr[i] + " "); 
System.out.println(); 
} 
// Main method 
public static void main(String args[]) 
{ 
int arr[] = {21, 11, 43, 5, 19, 7}; 
System.out.println("Given Array"); 
printArray(arr); 
MergeSort ob = new MergeSort(); 
ob.sort(arr, 0, arr.length-1); 
System.out.println("\nSorted array"); 
printArray(arr); 
} 
} 

Output:

Given array is
21 11 43 5 19 7

Sorted array is
5 7 11 21 19 43

Advantages

  • Merge sort can be applied to any size of data collection.
  • Time complexity in all cases worst, average and best is O(n log n), which makes it very efficient.
  • This is a Stable sorting algorithm.
  • During the run-creation step, reading of the input is sequential ==> Not much seeking.
  • This is a highly parallelizable algorithm.
  • When heap sort is used for the in-memory part of the merge, its operation can be overlapped with I/O.
  • Tapes can be used since I/O is largely sequential.

Disadvantages

  • This is not an in-place sorting algorithm so extra memory space required proportional to n.
  • This is slower than the Quicksort when sorting large data.
  • Merge sort is comparatively less efficient than Quicksort.

Real-Time Application

An e-commerce website “You might like” section is the best example of a merge sort. You all must notice this section whenever you visit the site. They have maintained an array of all user account and their choices by the time whenever you visit the site for any purpose. Then they start recommending what you have bought and what you like. In this sorting, the more the number of inversions, the more dissimilar choices are there and fewer inversions mean more similar choices are there.

Other Sorting Algorithm

Author: Paridhi Joshi

Paridhi Joshi is an expert web content manager with significant experience in content creation. Professionally she is dedicated to staying up to date with the latest trends and technologies in content writing and committed to bringing state-of-the-art web approaches to the workplace. She is an efficient multi-tasker who can complete multiple projects under strict deadlines.

Leave a Reply

Your email address will not be published. Required fields are marked *