01: /**
02:    This class sorts an array, using the merge sort algorithm.
03: */
04: public class MergeSorter
05: {
06:    /**
07:       Constructs a merge sorter.
08:       @param anArray the array to sort
09:    */
10:    public MergeSorter(int[] anArray)
11:    {
12:       a = anArray;
13:    }
14:    
15:    /**
16:       Sorts the array managed by this merge sorter.
17:    */
18:    public void sort()
19:    {  
20:       if (a.length <= 1) return;
21:       int[] first = new int[a.length / 2];
22:       int[] second = new int[a.length - first.length];
23:       System.arraycopy(a, 0, first, 0, first.length);
24:       System.arraycopy(a, first.length, second, 0, second.length);
25:       MergeSorter firstSorter = new MergeSorter(first);
26:       MergeSorter secondSorter = new MergeSorter(second);
27:       firstSorter.sort();
28:       secondSorter.sort();
29:       merge(first, second);
30:    }
31: 
32:    /**
33:       Merges two sorted arrays into the array managed by this
34:       merge sorter. 
35:       @param first the first sorted array
36:       @param second the second sorted array
37:    */
38:    private void merge(int[] first, int[] second)
39:    {  
40:       // Merge both halves into the temporary array
41: 
42:       int iFirst = 0;
43:          // Next element to consider in the first array
44:       int iSecond = 0;
45:          // Next element to consider in the second array
46:       int j = 0; 
47:          // Next open position in a
48: 
49:       // As long as neither iFirst nor iSecond past the end, move
50:       // the smaller element into a
51:       while (iFirst < first.length && iSecond < second.length)
52:       {  
53:          if (first[iFirst] < second[iSecond])
54:          {  
55:             a[j] = first[iFirst];
56:             iFirst++;
57:          }
58:          else
59:          {  
60:             a[j] = second[iSecond];
61:             iSecond++;
62:          }
63:          j++;
64:       }
65: 
66:       // Note that only one of the two calls to arraycopy below
67:       // copies entries
68: 
69:       // Copy any remaining entries of the first array
70:       System.arraycopy(first, iFirst, a, j, first.length - iFirst);
71:       
72:       // Copy any remaining entries of the second half
73:       System.arraycopy(second, iSecond, a, j, second.length - iSecond);
74:    }
75: 
76:    private int[] a;
77: }