What is Merge Sort
Merge Sort is a sorting algorithm that uses the "divide and conquer" approach to sort an array of elements. It breaks down the input array into smaller and smaller sub-arrays until each sub-array contains only one element. It then merges these sub-arrays back together, in a sorted manner, until the entire original array is sorted.
Who invented it?
John von Neumann is often credited with the invention of Merge Sort, although the algorithm was independently discovered by several researchers, including James Stirling and Gene Amdahl.
Pseudocode
mergeSort(arr[], l, r)
if l < r
m = (l + r) / 2
mergeSort(arr, l, m)
mergeSort(arr, m+1, r)
merge(arr, l, m, r)
merge(arr[], l, m, r)
n1 = m - l + 1
n2 = r - m
L[1..n1], R[1..n2]
for i = 1 to n1
L[i] = arr[l + i - 1]
for j = 1 to n2
R[j] = arr[m + j]
i = 1, j = 1, k = l
while i <= n1 and j <= n2
if L[i] <= R[j]
arr[k] = L[i]
i = i + 1
else
arr[k] = R[j]
j = j + 1
k = k + 1
while i <= n1
arr[k] = L[i]
i = i + 1
k = k + 1
while j <= n2
arr[k] = R[j]
j = j + 1
k = k + 1
The Merge Sort algorithm can be broken down into two main parts: the merge() function and the mergeSort() function.
The merge() function takes three parameters: an array arr[], and two integers l and r, which denote the left and right boundaries of the subarray to be merged. The merge() function merges the two subarrays [l...m] and [m+1...r], where m is the middle index of the subarray. The function first calculates the sizes of the two subarrays, n1 and n2, and creates two temporary arrays L[] and R[] to hold the values of the subarrays. It then copies the elements of the subarrays into the temporary arrays, and then iterates through the two temporary arrays, comparing each element of L[] with each element of R[], and copying the smaller value into the original array arr[] until one of the subarrays has been fully merged into arr[]. Finally, any remaining elements in the subarray are copied into arr[].
The mergeSort() function takes three parameters: an array arr[], and two integers l and r, which denote the left and right boundaries of the subarray to be sorted. The mergeSort() function uses a divide-and-conquer approach to sort the subarray. It first checks if l is less than r, which indicates that there are still elements in the subarray to be sorted. If so, it calculates the middle index m of the subarray and recursively calls mergeSort() on the left and right halves of the subarray, from l to m and from m+1 to r. Finally, it calls the merge() function to merge the two halves of the subarray into a sorted array.
In summary, the mergeSort() function breaks down the original array into smaller and smaller subarrays, sorts each subarray using the merge() function, and then merges these sorted subarrays back together until the entire original array is sorted.
The merge() function takes three parameters: an array arr[], and two integers l and r, which denote the left and right boundaries of the subarray to be merged. The merge() function merges the two subarrays [l...m] and [m+1...r], where m is the middle index of the subarray. The function first calculates the sizes of the two subarrays, n1 and n2, and creates two temporary arrays L[] and R[] to hold the values of the subarrays. It then copies the elements of the subarrays into the temporary arrays, and then iterates through the two temporary arrays, comparing each element of L[] with each element of R[], and copying the smaller value into the original array arr[] until one of the subarrays has been fully merged into arr[]. Finally, any remaining elements in the subarray are copied into arr[].
The mergeSort() function takes three parameters: an array arr[], and two integers l and r, which denote the left and right boundaries of the subarray to be sorted. The mergeSort() function uses a divide-and-conquer approach to sort the subarray. It first checks if l is less than r, which indicates that there are still elements in the subarray to be sorted. If so, it calculates the middle index m of the subarray and recursively calls mergeSort() on the left and right halves of the subarray, from l to m and from m+1 to r. Finally, it calls the merge() function to merge the two halves of the subarray into a sorted array.
In summary, the mergeSort() function breaks down the original array into smaller and smaller subarrays, sorts each subarray using the merge() function, and then merges these sorted subarrays back together until the entire original array is sorted.
Sample Code
// C++ code snippet
// Merge function to merge two sorted subarrays
void merge(vector& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary arrays
vector L(n1), R(n2);
// Copy data into temporary arrays
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// Merge the two sorted subarrays
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy any remaining elements of L[] and R[] back into arr[]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Merge Sort function
void mergeSort(vector& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// Recursively sort left and right halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
int main() {
// Example usage of Merge Sort
vector arr = { 12, 11, 13, 5, 6, 7 };
int n = arr.size();
mergeSort(arr, 0, n - 1);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
# Python code snippet
def merge(arr, left, mid, right):
n1 = mid - left + 1
n2 = right - mid
# Create temporary arrays
L = arr[left:left+n1]
R = arr[mid+1:mid+1+n2]
# Merge the two sorted subarrays
i = j = 0
k = left
while i < n1 and j < n2:
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# Copy any remaining elements of L[] and R[] back into arr[]
while i < n1:
arr[k] = L[i]
i += 1
k += 1
while j < n2:
arr[k] = R[j]
j += 1
k += 1
def mergeSort(arr, left, right):
if left < right:
# Find the middle index
mid = (left + right) // 2
# Recursively sort left and right halves
mergeSort(arr, left, mid)
mergeSort(arr, mid+1, right)
# Merge the sorted halves
merge(arr, left, mid, right)
# Example usage of Merge Sort
arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
mergeSort(arr, 0, n-1)
print("Sorted array:", arr)
import java.util.Arrays;
public class MergeSort {
// Merge function to merge two sorted subarrays
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary arrays
int[] L = Arrays.copyOfRange(arr, left, left + n1);
int[] R = Arrays.copyOfRange(arr, mid + 1, mid + 1 + n2);
// Merge the two sorted subarrays
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy any remaining elements of L[] and R[] back into arr[]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Merge Sort function
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// Recursively sort left and right halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
public static void main(String[] args) {
// Example usage of Merge Sort
int[] arr = {12, 11, 13, 5, 6, 7};
int n = arr.length;
mergeSort(arr, 0, n - 1);
System.out.print("Sorted array: ");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
Time and Space Complexity
Time Complexity:
The Merge Sort algorithm has a time complexity of O(nlogn) in the worst, best, and average case. This is because the algorithm divides the input array into smaller halves and recursively sorts them. The time complexity of dividing the array into halves is O(logn), and the time complexity of merging the sorted halves is O(n). Therefore, the total time complexity of Merge Sort is O(nlogn) as the algorithm performs logn divisions and each division takes O(n) time.
Space Complexity:
The Merge Sort algorithm has a space complexity of O(n) in the worst case. This is because the algorithm creates temporary arrays to store the divided subarrays during the merge phase of the algorithm. The size of the temporary arrays is equal to the size of the original array, so the space complexity is O(n). However, in the best case, the space complexity can be reduced to O(logn) because the algorithm performs logn divisions, and each division only requires a constant amount of memory.
The Merge Sort algorithm has a time complexity of O(nlogn) in the worst, best, and average case. This is because the algorithm divides the input array into smaller halves and recursively sorts them. The time complexity of dividing the array into halves is O(logn), and the time complexity of merging the sorted halves is O(n). Therefore, the total time complexity of Merge Sort is O(nlogn) as the algorithm performs logn divisions and each division takes O(n) time.
Space Complexity:
The Merge Sort algorithm has a space complexity of O(n) in the worst case. This is because the algorithm creates temporary arrays to store the divided subarrays during the merge phase of the algorithm. The size of the temporary arrays is equal to the size of the original array, so the space complexity is O(n). However, in the best case, the space complexity can be reduced to O(logn) because the algorithm performs logn divisions, and each division only requires a constant amount of memory.
Advantages
- Efficient for sorting large datasets: Merge Sort has a time complexity of O(n*logn) in the worst case, making it an efficient algorithm for sorting large datasets.
- Stable sorting algorithm: Merge Sort is a stable sorting algorithm, which means that the order of equal elements is preserved during the sorting process. This is useful when sorting objects with multiple keys or attributes.
- Well-suited for parallel processing: The divide-and-conquer approach of Merge Sort is well-suited for parallel processing, making it possible to implement the algorithm in a distributed computing environment.
Disadvantages
- Space complexity: Merge Sort requires additional memory to store the divided subarrays during the merge phase of the algorithm, making it less space-efficient than some other sorting algorithms.
- Recursive nature: The recursive nature of Merge Sort can be inefficient for small datasets, as the overhead of the recursive calls can outweigh the benefits of the algorithm.
- Not an in-place algorithm: Merge Sort requires additional memory to store the divided subarrays during the merge phase of the algorithm, making it an out-of-place sorting algorithm. This can be a disadvantage in applications with limited memory or where the input data is stored in a disk or external storage.
- In summary, Merge Sort is a highly efficient sorting algorithm with stable sorting properties and suitability for parallel processing. However, its space complexity and recursive nature may limit its performance in certain applications.