Merge Sort – Data Structure and Algorithms Tutorials
**Merge sort** is a sorting algorithm that follows the **divide-and-conquer** approach. It works by recursively dividing the input array into smaller subarrays and sorting those subarrays then merging them back together to obtain the sorted array.
In simple terms, we can say that the process of **merge sort** is to divide the array into two halves, sort each half, and then merge the sorted halves back together. This process is repeated until the entire array is sorted.
.png)
Merge Sort Algorithm
How does Merge Sort work?
Merge sort is a popular sorting algorithm known for its efficiency and stability. It follows the **divide-and-conquer** approach to sort a given array of elements.
Here’s a step-by-step explanation of how merge sort works:
- **Divide:** Divide the list or array recursively into two halves until it can no more be divided.
- **Conquer:** Each subarray is sorted individually using the merge sort algorithm.
- **Merge:** The sorted subarrays are merged back together in sorted order. The process continues until all elements from both subarrays have been merged.
Illustration of Merge Sort:
Let’s sort the array or list **[38, 27, 43, 10]** using Merge Sort
Let’s look at the working of above example:
**Divide:**
- **[38, 27, 43, 10]** is divided into **[38, 27] and **[43, 10]**.
- **[38, 27]** is divided into **[38]** and **[27]**.
- **[43, 10]** is divided into **[43]** and **[10]**.
**Conquer:**
- **[38]** is already sorted.
- **[27]** is already sorted.
- **[43]** is already sorted.
- **[10]** is already sorted.
**Merge:**
- Merge **[38]** and **[27]** to get **[27, 38]**.
- Merge **[43]** and **[10]** to get **[10,43]**.
- Merge **[27, 38]** and **[10,43]** to get the final sorted list **[10, 27, 38, 43]**
Therefore, the sorted list is **[10, 27, 38, 43]**.
Recommended PracticeMerge SortTry It!Implementation of Merge Sort:
C++
// C++ program for Merge Sort
#include <bits/stdc++.h>
using namespace std;
// Merges two subarrays of array[].
// First subarray is arr[begin..mid]
// Second subarray is arr[mid+1..end]
void merge(int array[], int const left, int const mid,
int const right)
{
int const subArrayOne = mid - left + 1;
int const subArrayTwo = right - mid;
// Create temp arrays
auto *leftArray = new int[subArrayOne],
*rightArray = new int[subArrayTwo];
// Copy data to temp arrays leftArray[] and rightArray[]
for (auto i = 0; i < subArrayOne; i++)
leftArray[i] = array[left + i];
for (auto j = 0; j < subArrayTwo; j++)
rightArray[j] = array[mid + 1 + j];
auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0;
int indexOfMergedArray = left;
// Merge the temp arrays back into array[left..right]
while (indexOfSubArrayOne < subArrayOne
&& indexOfSubArrayTwo < subArrayTwo) {
if (leftArray[indexOfSubArrayOne]
<= rightArray[indexOfSubArrayTwo]) {
array[indexOfMergedArray]
= leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
}
else {
array[indexOfMergedArray]
= rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
}
indexOfMergedArray++;
}
// Copy the remaining elements of
// left[], if there are any
while (indexOfSubArrayOne < subArrayOne) {
array[indexOfMergedArray]
= leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
indexOfMergedArray++;
}
// Copy the remaining elements of
// right[], if there are any
while (indexOfSubArrayTwo < subArrayTwo) {
array[indexOfMergedArray]
= rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
indexOfMergedArray++;
}
delete[] leftArray;
delete[] rightArray;
}
// begin is for left index and end is right index
// of the sub-array of arr to be sorted
void mergeSort(int array[], int const begin, int const end)
{
if (begin >= end)
return;
int mid = begin + (end - begin) / 2;
mergeSort(array, begin, mid);
mergeSort(array, mid + 1, end);
merge(array, begin, mid, end);
}
// UTILITY FUNCTIONS
// Function to print an array
void printArray(int A[], int size)
{
for (int i = 0; i < size; i++)
cout << A[i] << " ";
cout << endl;
}
// Driver code
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
cout << "Given array is \n";
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
cout << "\nSorted array is \n";
printArray(arr, arr_size);
return 0;
}
// This code is contributed by Mayank Tyagi
// This code was revised by Joshua Estes
C
Java
C#
Javascript
PHP
Output
Given array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13
**Complexity Analysis of Merge Sort:** ——————————————
**Time Complexity:**
- **Best Case:** O(n log n), When the array is already sorted or nearly sorted.
- **Average Case:** O(n log n), When the array is randomly ordered.
- **Worst Case:** O(n log n), When the array is sorted in reverse order.
**Space Complexity:** O(n), Additional space is required for the temporary array used during merging.
**Advantages of Merge Sort:**
- **Stability**: Merge sort is a stable sorting algorithm, which means it maintains the relative order of equal elements in the input array.
- **Guaranteed worst-case performance:** Merge sort has a worst-case time complexity of **O(N logN)**, which means it performs well even on large datasets.
- **Simple to implement:** The divide-and-conquer approach is straightforward.
**Disadvantage of Merge Sort:**
- **Space complexity:** Merge sort requires additional memory to store the merged sub-arrays during the sorting process.
- **Not in-place:** Merge sort is not an in-place sorting algorithm, which means it requires additional memory to store the sorted data. This can be a disadvantage in applications where memory usage is a concern.
Applications of Merge Sort:
- Sorting large datasets
- External sorting (when the dataset is too large to fit in memory)
- Inversion counting (counting the number of inversions in an array)
- Finding the median of an array
**Quick Links:**
- Recent Articles on Merge Sort
- Top Sorting Interview Questions and Problems
- Practice problems on Sorting algorithm
- Quiz on Merge Sort