Introduction To Merge Sort
Organizing any data into arrays with plentiful sorting techniques can be intimidating and confusing, especially for a beginner. I got you covered!
In this article, I have ‘divided and combined’ the nuances of one such sorting technique- ‘Merge sort’, which is an easy and widely used algorithm for sorting arrays.
Unlike other sorting algorithms that work on the brute-force approach, merge sort is based on the ‘divide and conquer’ approach. As the name suggests, in this approach, the array is first broken down (‘divided’) into smaller sub-arrays. These sub-arrays are considered individual arrays and are divided further. The process continues so forth until we get a single element in each array (‘conquer’). After which, we combine the elements in the desired order.
Here it should be noted that if the initial array has just one element, then it is considered sorted.
Merge sort follows this approach to sort the data recursively. Therefore it requires lesser time than other algorithms.
The working mechanism of Merge Sort –
Let us consider we have an array having 12 elements. Using merge sort, we will divide the array into two sub-arrays containing 6 elements each. So we have two arrays with 6 elements each. Later, each of these arrays is divided into two more arrays containing 3 elements each. At this stage, we have four arrays, 3 elements in each. These individual arrays will be again divided into two sub-arrays, one with 2 elements and the other with 1 element. After this step, we have eight arrays, four arrays 2 elements and four with single elements. Now, leaving the single elements untouched, we will break the four arrays of 2 elements into 8 sub-arrays each having a single element. After this, we would have reached the end of the dividing part, since we have 8+4=12 single elements.
Now, these single elements have to be combined. For instance, let us arrange them in ascending order. The combining step will start from the sub-level after which we have bigger arrays. These bigger arrays are further combined in order until we have an array of 12 elements arranged in order. The conquering and merging end here, and hence we have a final sorted array.
Example:
Sort the following array of 7 elements using merge sort.
This is the final sorted array.
Consider another example.
This is how a recursive tree can be drawn.
Merge sort Algorithm -
Merge_sort(A, low, high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
Merge_sort(A,low,mid);
Merge_sort(A,mid+1,high);
Merge(A,low,mid,high);
}
// Merge sort concepts starts here
Merge(A,low,mid,high)
{
i = low;
k = low;
j = mid + 1;
while (i <= mid && j <= high){
if (a[i] < =a[j]){
b[k] = a[i];
k++;
i++;
}
else{
b[k] = a[j];
k++;
j++;
}
}
if(i>mid){
while (j <= high){
b[k] = a[j];
k++;
j++;
}
}
else{
while (i <= mid){
b[k] = a[i];
k++;
i++;
}
}
for (k = low; k <=high ; k++){
a[k] = b[k];
}
}
Time Complexity-
Advantages and disadvantages-
· It is quicker for larger data and lists because it doesn’t run through the whole list repeatedly. But it is time-consuming for smaller arrays.
· Merge sort has a consistent running time. But it uses more memory space to store each element of the initially divided array.
Hope this was a help. Keep going!
