Merge Sort Algorithm
The Merge Sort algorithm is a sorting algorithm that is based on the Divide and
Conquer paradigm. In this algorithm, the array is initially divided into two equal halves and then
they are combined in a sorted manner.
Merge Sort Working Process:
Think of it as a recursive algorithm continuously splits the array in half until it cannot be further
divided. This means that if the array becomes empty or has only one element left, the dividing
will stop, i.e. it is the base case to stop the recursion. If the array has multiple elements, split the
array into halves and recursively invoke the merge sort on each of the halves. Finally, when both
halves are sorted, the merge operation is applied. Merge operation is the process of taking two
smaller sorted arrays and combining them to eventually make a larger one.
Illustration:
To know the functioning of merge sort, lets consider an array arr[] = {38, 27, 43, 3, 9, 82, 10}
At first, check if the left index of array is less than the right index, if yes then calculate its
mid point
Now, as we already know that merge sort first divides the whole array iteratively into equal
halves, unless the atomic values are achieved.
Here, we see that an array of 7 items is divided into two arrays of size 4 and 3 respectively.
Now, again find that is left index is less than the right index for both arrays, if found yes,
then again calculate mid points for both the arrays.
Now, further divide these two arrays into further halves, until the atomic units of the array
is reached and further division is not possible.
After dividing the array into smallest units, start merging the elements again based on
comparison of size of elements
Firstly, compare the element for each list and then combine them into another list in a
sorted manner.
After the final merging, the list looks like this:
The following diagram shows the complete merge sort process for an example array {38, 27,
43, 3, 9, 82, 10}.
If we take a closer look at the diagram, we can see that the array is recursively divided into two
halves till the size becomes 1. Once the size becomes 1, the merge processes come into action
and start merging arrays back till the complete array is merged.
step 1: start
step 2: declare array and left, right, mid variable
step 3: perform merge function.
if left > right
return
mid= (left+right)/2
mergesort(array, left, mid)
mergesort(array, mid+1, right)
merge(array, left, mid, right)
step 4: Stop
Follow the steps below the solve the problem:
MergeSort(arr[], l, r)
If r > l
Find the middle point to divide the array into two halves:
middle m = l + (r – l)/2
Call mergeSort for first half:
Call mergeSort(arr, l, m)
Call mergeSort for second half:
Call mergeSort(arr, m + 1, r)
Merge the two halves sorted in steps 2 and 3:
Call merge(arr, l, m, r)
// C++ program for Merge Sort
#include <iostream>
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)
{
auto const subArrayOne = mid - left + 1;
auto 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, // Initial index of first sub-array
indexOfSubArrayTwo
= 0; // Initial index of second sub-array
int indexOfMergedArray
= left; // Initial index of merged array
// 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; // Returns recursively
auto 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 (auto i = 0; i < size; i++)
cout << A[i] << " ";
}
// Driver code
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
auto 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
