The merge sort algorithm can be described recursively as follows : The algorithm divides the array into two halves and applies merge sort on each half recursively. After the two halves are sorted, merge them. The algorithm is described in Listing 23.4.
1 public static void mergeSort( int [] list) { 2 if (list.length > 1 ) { 3 mergeSort(list[ ... list.length / 2 ]); 4 mergeSort(list[list.length / 2 + 1 ... list.length]); 5 merge list[ ... list.length / 2 ] with 6 list[list.length / 2 + 1 ... list.length]; 7 } 8 } |
Figure 23.2 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 merge sort on this two subarrays recursively to split (1 9 5 4) into (1 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 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).
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 method for merging two sorted arrays is given in Listing 23.5.
1 private static int [] merge( int [] list1, int [] list2) { 2 int [] temp = new int [list1.length + list2.length]; 3 4 int current1 = ; // Index in list1 5 int current2 = ; // Index in list2 6 int current3 = ; // Index in temp 7 8 while (current1 < list1.length && current2 < list2.length) { 9 if (list1[current1] < list2[current2]) 10 temp[current3++] = list1[current1++]; 11 else 12 temp[current3++] = list2[current2++]; 13 } 14 15 while (current1 < list1.length) 16 temp[current3++] = list1[current1++]; 17 18 while (current2 < list2.length) 19 temp[current3++] = list2[current2++]; 20 21 return temp; 22 } |
This method merges arrays list1 and list2 into a temporary array temp . So, temp.length is list1.length + list2.length (line 2). current1 and current2 point to the current element to be considered in list1 and list2 (lines 4 “5). The method repeatedly compares the current elements from list1 and list2 and moves the smaller one to temp . current1 is increased by 1 (line 10) if the smaller one is in list1 and current2 is increased by 1 (line 12) 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 15 “16). If there are still unmoved elements in list2 , copy them to temp (lines 18 “19). The method returns temp as the new sorted array in line 21.
Figure 23.3 illustrates how to merge 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 23.3(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 23.3(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 23.3(c).
The merge sort algorithm is implemented in Listing 23.6.
1 public class MergeSort { 2 /** The method for sorting the numbers */ 3 public static void mergeSort( int [] list) { 4 if (list.length > 1 ) { 5 // Merge sort the first half 6 int [] firstHalf = new int [list.length / 2 ]; 7 System.arraycopy(list, , firstHalf, , list.length / 2 ); 8 mergeSort(firstHalf); 9 10 // Merge sort the second half 11 int secondHalfLength = list.length - list.length / 2 ; 12 int [] secondHalf = new int [secondHalfLength]; 13 System.arraycopy(list, list.length / 2 , 14 secondHalf, , secondHalfLength); 15 mergeSort(secondHalf); 16 17 // Merge firstHalf with secondHalf 18 int [] temp = merge(firstHalf, secondHalf); 19 System.arraycopy(temp, , list, , temp.length); 20 } 21 } 22 23 private static int [] merge( int [] list1, int [] list2) { 24 // Same as in Listing 23.5, so omitted 25 } 26 } |
The algorithm creates a new array firstHalf , which is a copy of the first half of list (line 7). The algorithm invokes mergeSort recursively on firstHalf (line 8). 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 15). After firstHalf and secondHalf are sorted, they are merged to become a new sorted array in temp (line 18). Finally, temp is assigned to the original array list (line 19). So, array list is now sorted.
Let T ( n ) denote the time required for sorting an array of n elements using 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. So,
The first is the time for sorting the first half of the array and the second 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. So, the total time is 2 n - 1. Therefore,
The complexity of merge sort is O ( n log n ). This algorithm is better than selection sort, insertion sort, and bubble sort. The sort method in the java.util.Arrays class is implemented using a variation of the merge sort algorithm.