Merge Sort
Tags: java, programming, beginners, learning
Published: 2024-07-17 11:57:56

The merge sort algorithm can be described recursively as follows: The algorithm divides the array into two halves and applies a merge sort on each half recursively. After the two halves are sorted, merge them.

The algorithm for a merge sort is given in code below:

 `public static void mergeSort(int[] list) {
 if (list.length > 1) {
 mergeSort(list[0 ... list.length / 2]);
 mergeSort(list[list.length / 2 + 1 ... list.length]);
 merge list[0 ... list.length / 2] with
 list[list.length / 2 + 1 ... list.length];
 }
 }`

Figure below illustrates a merge sort of an array of eight elements (2 9 5 4 8 1 6 7). The original array is split into (2 9 5 4) and (8 1 6 7). Apply a merge sort on these two subarrays recursively to split (2 9 5 4) into (2 9) and (5 4) and (8 1 6 7) into (8 1) and (6 7). This process continues until the subarray contains only one element. For example, array (2 9) is split into the subarrays (2) and (9). Since array (2) contains a single element, it cannot be further split. Now merge (2) with (9) into a new sorted array (2 9); merge (5) with (4) into a new sorted array (4 5). Merge (2 9) with (4 5) into a new sorted array (2 4 5 9), and finally merge (2 4 5 9) with (1 6 7 8) into a new sorted array (1 2 4 5 6 7 8 9).

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7oc3ljbettsx85fleofl.png)

The recursive call continues dividing the array into subarrays until each subarray contains only one element. The algorithm then merges these small subarrays into larger sorted subarrays until one sorted array results.

The merge sort algorithm is implemented in the code below:

```
package demo;

public class MergeSort {
	/** The method for sorting the numbers */
	public static void mergeSort(int[] list) {
		if(list.length > 1) {
			// Merge sort the first half
			int[] firstHalf = new int[list.length / 2];
			System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
			mergeSort(firstHalf);
			
			// Merge sort the second half
			int secondHalfLength = list.length - list.length / 2;
			int[] secondHalf = new int[secondHalfLength];
			System.arraycopy(list, list.length / 2, secondHalf, 0, secondHalfLength);
			mergeSort(secondHalf);
			
			// Merge firstHalf with seocndHalf into list
			merge(firstHalf, secondHalf, list);
		}
	}
	
	/** Merge two sorted lists */
	public static void merge(int[] list1, int[] list2, int[] temp) {
		int current1 = 0; // Current index in list1
		int current2 = 0; // Current index in list2
		int current3 = 0; // Current index in temp
		
		while(current1 < list1.length && current2 < list2.length) {
			if(list1[current1] < list2[current2])
				temp[current3++] = list1[current1++];
			else
				temp[current3++] = list2[current2++];
		}
		
		while(current1 < list1.length)
			temp[current3++] = list1[current1++];
		
		while(current2 < list2.length)
			temp[current3++] = list2[current2++];
	}

	public static void main(String[] args) {
		int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
		mergeSort(list);
		for(int i = 0; i < list.length; i++)
			System.out.print(list[i] + " ");
	}

}

```

The **mergeSort** method (lines 5–21) creates a new array **firstHalf**, which is a copy of the first half of **list** (line 9). The algorithm invokes **mergeSort** recursively on **firstHalf** (line 10). The length of the **firstHalf** is **list.length / 2** and the length of the **secondHalf** is **list.length - list.length / 2**. The new array **secondHalf** was created to contain the second part of the original array **list**. The algorithm invokes **mergeSort** recursively on **secondHalf** (line 16). After **firstHalf** and **secondHalf** are sorted, they are merged to **list** (line 19). Thus, array **list** is now sorted.

The **merge** method (lines 24–41) merges two sorted arrays **list1** and **list2** into array **temp**. **current1** and **current2** point to the current element to be considered in **list1** and **list2** (lines 25–27). The method repeatedly compares the current elements from **list1** and **list2** and moves the smaller one to **temp**. **current1** is increased by **1** (line 31) if the smaller one is in **list1** and **current2** is increased by **1** (line 33) if the smaller one is in **list2**. Finally, all the elements in one of the lists are moved to **temp**. If there are still unmoved elements in **list1**, copy them to **temp** (lines 36–37). If there are still unmoved elements in **list2**, copy them to **temp** (lines 39–40).

Figure below illustrates how to merge the two arrays **list1** (2 4 5 9) and **list2** (1 6 7 8). Initially the current elements to be considered in the arrays are 2 and 1. Compare them and move the smaller element 1 to **temp**, as shown in Figure below (a). **current2** and **current3** are increased by 1. Continue to compare the current elements in the two arrays and move the smaller one to **temp** until one of the arrays is completely moved. As shown in Figure below (b), all the elements in **list2** are moved to **temp** and **current1** points to element 9 in **list1**. Copy 9 to **temp**, as shown in Figure below (c).

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jnccdh4bdwargu1exjo4.png)

The **mergeSort** method creates two temporary arrays (lines 8, 14) during the dividing process, copies the first half and the second half of the array into the temporary arrays (lines 8, 15), sorts the temporary arrays (lines 10, 16), and then merges them into the original array (line 19), as shown in Figure below (a). You can rewrite the code to recursively sort the first half of the array and the second half of the array without creating new temporary arrays, and then merge the two arrays into a temporary array and copy its contents to the original array, as shown in Figure below (b).

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/af1of4dzr6e6tzyb2xwx.png)

A merge sort can be implemented efficiently using parallel processing.

Let T(n) denote the time required for sorting an array of n elements using a merge sort. Without loss of generality, assume n is a power of 2. The merge sort algorithm splits the array into two subarrays, sorts the subarrays using the same algorithm recursively, and then merges the subarrays. Therefore,

`T(n) = T(n / 2) + T(n / 2) + mergetime`

The first T(n / 2) is the time for sorting the first half of the array, and the second T(n / 2) is the time for sorting the second half. To merge two subarrays, it takes at most n - 1 comparisons to compare the elements from the two subarrays and n moves to move elements to the temporary array. Thus, the total time is 2n - 1. Therefore,

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/a9qtjdekw9narbevr65t.png)

The complexity of a merge sort is O(n logn). This algorithm is better than selection sort, insertion sort, and bubble sort, because the time complexity of these algorithms is O(n^2). The **sort** method in the **java.util.Arrays** class is implemented using a variation of the merge sort algorithm.