Updated April 5, 2023
Introduction of Merge Sort Algorithm
Merge sort is a divide-and-conquer algorithm based on the principle of breaking down a list into numerous sub-lists until each sub-list has only one element, then merging those sub-lists into a sorted list. The best case, average case, and worst-case running time complexity is O(n log(n)) time; the characteristics of the merge sort algorithm are as follows –
- Subdivide the unsorted list into N sublists, each containing an element.
- Combine adjacent pairings of two singleton lists to generate a list with two elements. N will now be converted into N/2 two-size lists.
- Repeat the process until you have a single sorted list.
Working of the Merge Sort Algorithm
Let take an example to understand the working of the merge sort algorithm –
The given array is [ 11, 6, 3, 24, 46, 22, 7 ], an array is subdivided into several sub-arrays in this method. Each sub-array is solved separately.
- The merge sort divides the entire array into two equal parts iteratively until the single values are reached. The array of 7 elements is split into two arrays, as shown below –
- This has no effect on the order in which elements appear in the original array. Now again, split these two arrays in half.
- Again divide these arrays until we reach the single value that can no longer be divided.
- Next, compare the elements in each list, then merge them in a sorted manner into another list. For example, in the first list, compare 11 and 6, and reverse the order. Next, compare 3 and 24; they are in the correct order. Next, again compare 46 and 22 and put 22then 46. Next, keep 7 as it is.
- Next, compare the lists of two data values in the following iteration of the combining phase, then merge them into a list of found data values in sorted order.
- The list will look like this after the final merge.
The final answer is formed by combining sub-arrays as shown in the below image –
The pseudocode for merge sort algorithm –
procedure merge_Sort( var array )
if ( length of a == 1 ) return array
var a1 as array = array[0] ... array[n/2]
var a2 as array = array[n/2+1] ... array[n]
a1 = mergesort( a1 )
a2 = mergesort( a2 )
return merge( a1, a2 )
end procedure
procedure merge( var a1 as array, var a2 as array )
var a3 as array
while ( a1 and a2 are not empty )
if ( a1[0] > a2[0] )
add a2[0] to the end of a3
remove a2[0] from a2
else
add a1[0] to the end of a3
remove a1[0] from a1
end if
end while
while ( a has elements )
add a[0] to the end of c
remove a[0] from a
end while
while ( a2 is not empty )
add a2[0] to the end of a3
remove a2[0] from a2
end while
return a3
end procedureThe merge_Sort() method divides the array into two sub-arrays and calls recursively itself and merge() method.
The merge() method will combine two sub-arrays of the array, one of which includes starting and ending locations from start to mid, and the other of which has positions from mid+1 to the end. Next, both arrays’ starting elements are combined. The elements of both portions are then compared, with the smaller value being saved in the backup array. Finally, if one portion of the array reaches the end, all of the elements from the other part of the array are added to the auxiliary array in the same order as they exist.
Example of Merge Sort Algorithm
Example for the merge sort algorithm in Java to show the working of the algorithm –
Example #1
Code:
// The program can be tested in Eclipse IDE, JAVA 11
package jex;
import java.util.*;
public class mergeSortClass
{
public static void merge(int arr[], int beg, int mid, int end)
{
int l = mid - beg + 1;
int r = end - mid;
int a1[] = new int [l];
int a2[] = new int [r];
for (int i = 0; i < l; ++i)
a1[i] = arr[beg + i];
for (int j = 0; j < r; ++j)
a2[j] = arr[mid + 1+ j];
int i = 0, j = 0, k = beg;
while ( i<l && j<r )
{
if (a1[i] <= a2[j]) {
arr[k] = a1[i];
i++;
}
else
{
arr[k] = a2[j];
j++;
} k++;
}
while ( i < l )
{
arr[k] = a1[i];
i++;
k++;
}
while ( j < r )
{
arr[k] = a2[j];
j++;
k++;
}
}
public static void mergeSort(int arr[], int beg, int end)
{
if ( beg < end )
{
int mid = ( beg + end ) / 2;
mergeSort( arr, beg, mid );
mergeSort( arr , mid+1, end );
merge( arr, beg, mid, end );
}
}
public static void main(String args[])
{
int array[] = { 40, 28, 38, 90, 76, 29, 67, 28, 31, 45 };
System.out.println( "The array before sorting is :" );
for(int i = 0; i < array.length; i++)
{
System.out.print(array[i]+ " ");
}
mergeSort( array, 0, array.length-1);
System.out.println( "\n\nThe array after sorting is :" );
for(int i =0; i < array.length; i++)
{
System.out.print(array[i]+ " ");
}
}
}Output:
As in the above program, the mergeSortClass class is created, which contains merge() and mergesort() methods. The merge() method merges the two arrays of the array where one array has starting and ending positions from start to mid, respectively, and another array has positions from mid+1 to the end. Next, corresponding elements of both the arrays are compared, and the small element assigns to the temporary array. When anyone array ends, then all the elements of another array are stored to the temporary array in the same order they are present. The mergeSort() method divides the array into two branches and calls itself recursively, and also calls the merge() method. In the main function, the array of numbers is and print the array before and after calling the mergeSort() method, as we can see in the above output.
Conclusion
Merge sort is a divide-and-conquer algorithm that divides a list into several sub-lists until each contains only one element, then merges the sub-lists into a sorted list. The best case, average case, and worst-case running time complexity are O(n log(n).
Recommended Articles
We hope that this EDUCBA information on “Merge Sort Algorithm” was beneficial to you. You can view EDUCBA’s recommended articles for more information.
