25.6. Sending and Receiving Objects

 
[Page 751]

23.4. Merge Sort

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.

Listing 23.4. Merge Sort Algorithm
 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).

Figure 23.2. Merge sort employs a divide-and-conquer approach to sort the array.


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.

Listing 23.5. Method for Merging Two Arrays
(This item is displayed on pages 751 - 752 in the print version)
 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 

[Page 752]
 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).

Figure 23.3. Two sorted arrays are merged into one sorted array.

The merge sort algorithm is implemented in Listing 23.6.

Listing 23.6. MergeSort.java
(This item is displayed on pages 752 - 753 in the print version)
 1   public class   MergeSort { 2  /** The method for sorting the numbers */  3   public static void   mergeSort(   int   [] list) { 

[Page 753]
 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.

23.4.1. Merge Sort Time

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,



[Page 754]

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.

 


Introduction to Java Programming-Comprehensive Version
Introduction to Java Programming-Comprehensive Version (6th Edition)
ISBN: B000ONFLUM
EAN: N/A
Year: 2004
Pages: 503

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net