Merge Sort
📘 Data Structure and Algorithm
👁 82 views
📅 Nov 05, 2025
⏱ Estimated reading time: 1 min
Merge Sort Algorithm
Merge Sort is a divide-and-conquer algorithm that splits an array into halves, sorts them recursively, and merges them back.
Algorithm Steps
- Divide the array into two halves.
- Recursively sort each half.
- Merge the sorted halves.
Example (C++)
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1, n2 = r - m;
int L[n1], R[n2];
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];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2)
arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
Time Complexity
- All Cases: O(n log n)
Advantages
- Stable and efficient for large data.
Disadvantages
- Requires extra space for merging.
Conclusion
Merge Sort is efficient and consistent, especially suitable for large datasets that need stable sorting.
🔒 Some advanced sections are available for Registered Members
Register Now
Register Now
Share this Post
← Back to Tutorials