Merge Sort
Merge Sort
Merge Sort is one of the most useful sorting algorithms and efficient sorting algorithm and it is based on the Divide and Conquer Algorithm principle. Mergesort is like to the quicksort algorithm and it uses the divide and conquer approach to sort the elements.
Algorithm
MergeSort(A, p, r):
if p > r
return
q = (p+r)/2
mergeSort(A, p, q)
mergeSort(A, q+1, r)
merge(A, p, q, r)
Example
Suppose the elements of array are –
According to the mergesort algorithm, firstly divide the given array into two equal parts.
There are eight elements in the given array, so it is divided them into two arrays of size four
Now, again divide two arrays into parts. As they have size 4, so divide into new arrays of size 2.
Again divide these divided arrays to get the atomic value that can’t be further divided.
And now combine these array in the same manner they were broken.
In combining, firstly, compare the element of each array and then combine these array into another array in sorted order.
So, first compare 12 and 31, they both are in sorted positions. After that compare the 25 and 8, and in the list of two values, put 8 first and then 25. Now, compare 32 and 17, sort them and put 17 first folthen put 32. Then, compare 40 and 42, and place these array in sequentially.
In the next iteration of combining, compare the arrays with two values and merge these arrays into an array of found values in sorted order.
Now, there is a final merging the arrays and the array look like –
Now,
Array is completely sorted
Program for merge sort in C
#include <stdio.h>
void merge(int arr[], int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
int L[n1], M[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];
int i, j, k;
i = 0;
j = 0;
k = p;
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = M[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = M[j];
j++;
k++;
}
}
// Divide the array into 2 subarrays, sort and merge them
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// Merge the sorted subarrays
merge(arr, l, m, r);
}
}
// Print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program
int main() {
int arr[] = {6, 5, 12, 10, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
printf("Sorted array: \n");
printArray(arr, size);
}
Output
Sorted array: 1 5 6 9 10 12
Program for merge sort in C++
#include <iostream>
using namespace std;
// Merge two subarrays
void merge(int arr[], int p, int q, int r) {
// Create L ← A[p..q] and M ← A[q+1..r]
int no1 = q - p + 1;
int no2 = r - q;
int L[no1], M[no2];
for (int i = 0; i < no1; i++)
L[i] = arr[p + i];
for (int j = 0; j < no2; j++)
M[j] = arr[q + 1 + j];
int i, j, k;
i = 0;
j = 0;
k = p;
while (i < no1 && j < no2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = M[j];
j++;
}
k++;
}
while (i < no1) {
arr[k] = L[i];
i++;
k++;
}
while (j < no2) {
arr[k] = M[j];
j++;
k++;
}
}
// Divide the array into two subarrays, sort and merge them
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// Merge the sorted subarrays
merge(arr, l, m, r);
}
}
// Print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {6, 5, 12, 10, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
cout << "Sorted array: \n";
printArray(arr, size);
return 0;
}
Output
Sorted array: 1 5 6 9 10 12
Program for merge sort in Python
def mergeSort(array):
if length(array) > 1:
a = length(array)//2
B = array[:r]
C = array[r:]
# Sort the two parts
mergeSort(B)
mergeSort(C)
i = j = k = 0
while i < length(B) and j < length(c):
if B[i] < B[j]:
array[k] = B[i]
i += 1
else:
array[k] = C[j]
j += 1
k += 1
while i < length(B):
array[k] = B[i]
i += 1
k += 1
while j < length(C):
array[k] = C[j]
j += 1
k += 1
# Print the array
def printList(array):
for i in range(length(array)):
print(array[i], end=" ")
print()
# Driver program
if __name__ == '__main__':
array = [6, 5, 12, 10, 9, 1]
mergeSort(array)
print("Sorted array is: ")
printList(array)
Output
Sorted array is: 1 5 6 9 10 12
Program for merge sort in Java
class MergeSort {
// Merge two subarrays
void merge(int arr[], int p, int q, int r) {
int no1 = q - p + 1;
int no2 = r - q;
int B[] = new int[no1];
int C[] = new int[no2];
for (int i = 0; i < no1; i++)
L[i] = arr[p + i];
for (int j = 0; j < no2; j++)
M[j] = arr[q + 1 + j];
// current index
int i, j, k;
i = 0;
j = 0;
k = p;
while (i < no1 && j < no2) {
if (B[i] <= C[j]) {
arr[k] = B[i];
i++;
} else {
arr[k] = B[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = B[i];
i++;
k++;
}
while (j < no2) {
arr[k] = C[j];
j++;
k++;
}
}
// Divide the array into 2 subarrays, sort and merge them
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(arr, b, c);
mergeSort(arr, c+ 1, r);
// Merge the sorted subarrays
merge(arr, b, c, r);
}
}
// Print the array
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver program
public static void main(String args[]) {
int arr[] = { 6, 5, 12, 10, 9, 1 };
MergeSort ob = new MergeSort();
ob.mergeSort(arr, 0, arr.length - 1);
System.out.println("Sorted array:");
printArray(arr);
}
}
Output
Sorted array: 1 5 6 9 10 12
Time Complexity
Best Case Complexity:
O(n*log n)
Worst Case Complexity:
O(n*log n)
Average Case Complexity:
O(n*log n)
Space Complexity
The space complexity is O(n).
Read more, Insertion sort