C Program to implement Merge Sort using Recursive Approach

Merge sort is a highly efficient sorting method that is particularly effective at organizing enormous datasets. The methodology employed is the divide-and-conquer strategy, which involves decomposing intricate issues into smaller, more feasible components. Allow me to explain the functioning of this:

1.   Partition: Consider a collection of numbers that is not arranged in any particular order. Merge sort initially divides the list into approximately equal halves. The process of dividing the list into sublists continues recursively until each sublist consists of only one member. 
2. Conquer: Once the sublists have been reduced to their shortest size, consisting of only one element each, they are naturally arranged in a sorted order. This step is known as the "conquering" stage, during which the subproblems are easily and straightforwardly addressed.
3. Combine: The enchantment occurs at this location. The sorted sublists are skillfully combined in a precise sequence. The merging procedure involves comparing elements from each sublist and integrating the smaller element into the final sorted list. The merging process continues until all sublists have been completely used, resulting in a main list that is completely sorted.

---

The Significance of Merge Sort

---

The brilliance of merge sort is seen in its high efficiency. The time complexity of merge sort is O(n log n), indicating that the time required for sorting increases in proportion to the logarithm of the number of items (n). Compared to methods such as bubble sort or selection sort, this approach is considerably faster, as its time complexity increases quadratically (O(n^2)).

---

Here are the distinguishing features of merge sort

---

Assured Efficiency: In contrast to certain sorting algorithms that may exhibit subpar performance in certain situations, merge sort consistently achieves a performance of O(n log n), independent of the initial order of the input data. 

Stability: Merge sort maintains the initial sequence of identical entries. This implies that if there are duplicate elements in your unsorted list, they will be arranged in the sorted list in the exact same sequence as they were initially seen. 

Flexibility: Merge sort can be executed by utilizing linked lists, rendering it appropriate for scenarios where memory allocation is a matter of concern.

 

The efficiency and reliability of merge sort make it widely used in numerous applications, such as sorting big datasets, implementing external sorting algorithms (for data that exceeds memory capacity), and counting inversions in a list.

Source Code

#include<stdlib.h> #include<stdio.h> void merge(int *list, 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 arrays L[] and R[] ; Basically L[] denotes the left subarray and R[] denotes right subarray*/ for (i = 0; i < n1; i++) L[i] = list[l + i]; for (j = 0; j < n2; j++) /*divide method for divide and conquer algorithm*/ R[j] = list[m + 1+ j]; /* Merge the temp arrays back into arr[l..r]*/ i = 0; // Initial index of first subarray j = 0; // Initial index of second subarray k = l; // Initial index of merged subarray while (i < n1 && j < n2) { if (L[i] <= R[j]) { list[k] = L[i]; i++; /*place the elements in their exact position based on comparisions*/ } /*conquer method which is basically combine*/ else { list[k] = R[j]; j++; } k++; } /* Copy the remaining elements of L[], if there are any */ while (i < n1) { list[k] = L[i]; i++; k++; } /* Copy the remaining elements of R[], if there are any */ while (j < n2) { list[k] = R[j]; j++; k++; } } /* l is for left index and r is right index of the sub-array of arr to be sorted */ void mergesort(int *list, 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(list, l, m); mergesort(list, m+1, r); merge(list, l, m, r); } } void display(int *list, int size) { int i; for (i=0; i < size; i++) printf("%d|", list[i]); } int main() { int i, low, high, n; int *list; printf("\nenter the no of elements:"); scanf("%d", &n); list=(int *)malloc(sizeof(int) * n); for(i = 0;i < n; i++) scanf("%d", &list[i]); low = 0; high = n - 1; mergesort(list, low, high); printf("\nsorted list is:\n"); display(list, n); return 0; }

---

Happy Exploring!