Merge Sort
Hola amigos. As a student of computer science, you all must have heard of the term sorting. If not, it’s just arranging the data in a specific manner. The domain of computer science keeps on increasing day by day and we come to see a lot of different types of algorithm people come up with in order to perform tasks faster. One of the best strategies till now is the divide and conquer approach.
Now what exactly is divide and conquer. As the name suggest we divide the whole list into smaller parts we perform operation which lead us to our goal and conquer the problem. Its as simple as that right? I am not going to scare you but it seems to be easy but there is more to it. The logic in dividing and merging takes a lot to think of than what it seems to. One of the algorithms which uses divide and conquer strategy is Merge Sort. In this blog we are going to talk about merge sort.
Merge Sort
One of the best sorting algorithms is the merge sort with a complexity of O(nlogn) in all the three cases i.e., best, worst and average. Here we divide the array into two halves, call itself for both the halves and then merge both the sorted halves. The basic algorithm is given below:
MergeSort (arr [], l, r)
If r > l
1. Find the middle point to divide the array into two halves:
middle m = l+ (r-l)/2
2. Call mergeSort for first half:
Call mergeSort (arr, l, m)
3. Call mergeSort for second half:
Call mergeSort (arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
Call merge (arr, l, m, r)
To represent in into pictorial form here is an image from Wikipedia which shows the intermediate steps to sort an array [38,27,43,3,9,82,10].
Now coming back to the Merge Sort algorithm. From the first line you can see that the middle position is calculated using the basic formula i.e.,
middle=start index+(end index-start index)/2
we call the mergesort (array, start, middle) function for first half and mergesort (array, middle+1, end) for the second half. Finally, a merge (array, left, middle, end) function to merge the sorted halves. This algorithm consecutively divides the array into two halves until the base condition arrives which is a single element then starts merging them as in a sorted manner. As you can see from the diagram given above.
This is a snippet of code what you actually do in mergesort.
Now the mergesort () function is quite easy. The main problem is how to merge the divided sorted subarrays so that the merged array is also sorted.
So, first of all we create two subarrays in the merge () function and assign them values according to the position of the element in that array. Now we run a loop comparing elements in both the subarrays and assigning value to the position of the original array as soon as we find that the comparison satisfies our condition (either in ascending or descending as per our requirement). What left for us is to check whether there still are some elements which are unchecked. If the answer is yes, then just append them in the same order they are left at the end of the array from both the subarrays.
A snippet of code what we have to do in merge sort is given below.
These snippets lack comments but once you read it, you’ll understand what I’ve done. Everything I have done in the code is what I have explained to you. If you have any doubts or complaints please do write it in the response box. I will definitely try to clear your doubts. Happy coding!!!
Below is the full code for merge sort in C++.
#include<iostream>
#include<cstdio>
using namespace std;
void merge(int *arr,int start,int mid,int end){
int size1=mid-start+1,size2=end-mid;
int leftarr[size1],rghtarr[size2];
for(int i=0;i<size1;i++)
leftarr[i]=arr[start+i];
for (int j=0;j<size2;j++)
rghtarr[j]=arr[mid+j+1];
int i = 0;
int j = 0;
int k = start;
while (i < size1 && j < size2) {
if (leftarr[i] <= rghtarr[j]) {
arr[k] = leftarr[i];
i++;
}
else {
arr[k] = rghtarr[j];
j++;
}
k++;
}
while (i < size1) {
arr[k] = leftarr[i];
i++;
k++;
}
while (j < size2) {
arr[k] = rghtarr[j];
j++;
k++;
}
}
void mergeSort(int *arr,int start,int end){
if(start>=end){
return;
}
int mid=(start+end)/2;
mergeSort(arr,start,mid);
mergeSort(arr,mid+1,end);
merge(arr,start,mid,end);
}
int main(){
int size;
cin>>size;
int arr[size];
for (int i=0;i<size;i++)
cin>>arr[i];
mergeSort(arr,0,size-1);
for (int i=0;i<size;i++)
cout<<arr[i]<<” “;
}
This sorting algorithm has time complexity of O(nlogn) for all the three cases. This will be the same even for already sorted array. On the other hand there are other sorting technique which is better for already sorted array.
