# MergeSorter.java.html

`  1  /**`
`  2     The sort method of this class sorts an array, using the merge `
`  3     sort algorithm.`
`  4  */`
`  5  public class MergeSorter`
`  6  {`
`  7     /**`
`  8        Sorts an array, using merge sort.`
`  9        @param a the array to sort`
` 10     */`
` 11     public static void sort(int[] a)`
` 12     {  `
` 13        if (a.length <= 1) { return; }`
` 14        int[] first = new int[a.length / 2];`
` 15        int[] second = new int[a.length - first.length];`
` 16        // Copy the first half of a into first, the second half into second`
` 17        for (int i = 0; i < first.length; i++) `
` 18        { `
` 19           first[i] = a[i]; `
` 20        }`
` 21        for (int i = 0; i < second.length; i++) `
` 22        { `
` 23           second[i] = a[first.length + i]; `
` 24        }`
` 25        sort(first);`
` 26        sort(second);`
` 27        merge(first, second, a);`
` 28     }`
` 29  `
` 30     /**`
` 31        Merges two sorted arrays into an array`
` 32        @param first the first sorted array`
` 33        @param second the second sorted array`
` 34        @param a the array into which to merge first and second`
` 35     */`
` 36     private static void merge(int[] first, int[] second, int[] a)`
` 37     {  `
` 38        int iFirst = 0; // Next element to consider in the first array`
` 39        int iSecond = 0; // Next element to consider in the second array`
` 40        int j = 0; // Next open position in a`
` 41  `
` 42        // As long as neither iFirst nor iSecond is past the end, move`
` 43        // the smaller element into a`
` 44        while (iFirst < first.length && iSecond < second.length)`
` 45        {  `
` 46           if (first[iFirst] < second[iSecond])`
` 47           {  `
` 48              a[j] = first[iFirst];`
` 49              iFirst++;`
` 50           }`
` 51           else`
` 52           {  `
` 53              a[j] = second[iSecond];`
` 54              iSecond++;`
` 55           }`
` 56           j++;`
` 57        }`
` 58  `
` 59        // Note that only one of the two loops below copies entries`
` 60        // Copy any remaining entries of the first array`
` 61        while (iFirst < first.length) `
` 62        { `
` 63           a[j] = first[iFirst]; `
` 64           iFirst++; j++;`
` 65        }`
` 66        // Copy any remaining entries of the second half`
` 67        while (iSecond < second.length) `
` 68        { `
` 69           a[j] = second[iSecond]; `
` 70           iSecond++; j++;`
` 71        }`
` 72     }`
` 73  }`