## 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 procedure

The 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

This is a guide to Merge Sort Algorithm. Here we also discuss the introduction and working of the merge sort algorithm along with examples and its code implementation. You may also have a look at the following articles to learn more –