Merge Sort (Divide and Conquer Technique)

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 for Merge Sort

#include<stdio.h> #include<stdlib.h> #include<math.h> void merge(int *arr, int lo, int mid, int hi){ int i, j, k; int size1 = (mid - lo + 1); int size2 = (hi - mid); int *mArr1 = (int *)malloc(size1 * sizeof(int)); int *mArr2 = (int *)malloc((size2) * sizeof(int)); for(i = 0; i < size1; i++){ mArr1[i] = arr[lo+i]; } for(i = 0; i < size2; i++){ mArr2[i] = arr[mid + 1 + i]; } i = 0, j = 0, k = lo; while(i < size1 && j < size2){ if(mArr1[i] <= mArr2[j]){ arr[k] = mArr1[i]; i++; } else{ arr[k] = mArr2[j]; j++; } k++; } while(i < size1){ arr[k] = mArr1[i]; k++; i++; } while(j < size2){ arr[k] = mArr2[j]; k++; j++; } } void mergeSort(int *arr, int start, int end){ if(end > start){ int mid = start + (end - start) / 2; mergeSort(arr, start, mid); mergeSort(arr, mid + 1, end); merge(arr, start, mid, end); } } int main() { int *arr, n, i; printf("Enter size of array:"); scanf("%d", &n); printf("Enter items of the array:"); for(i = 0; i < n; i++) { scanf("%d", &arr[i]); } mergeSort(arr, 0, n-1); for(i = 0; i < n; i++) { printf("%d", arr[i]); } return 0; }

---

Happy Exploring!