import java.util.Arrays; /** * The sort method of this class sorts an array, using the merge sort algorithm. */ public class MergeSorter { /** * Sort an array, using merge sort. * @param a the array to sort */ public static void sort(int[] a) { if (a.length <= 1) return; int[] first = new int[a.length/2]; int[] second = new int[a.length - first.length]; // Copy the first half of a into first // and the second half into second for (int i = 0; i < first.length; i++) { first[i] = a[i]; } for (int i = 0; i < second.length; i++) { second[i] = a[first.length + i]; } // Recursively sort each half. sort(first); sort(second); // Merge the two sorted halves back // into a single sorted array. merge(first, second, a); } /** * Merge two sorted arrays into a single sorted array. * @param first the first sorted array * @param second the second sorted array * @param a the array into which to merge first and second */ private static void merge(int[] first, int[] second, int[] a) { int iFirst = 0; // Next element to consider in the first array int iSecond = 0; // Next element to consider in the second array int j = 0; // Next open position in a // As long as neither iFirst nor iSecond is past the end, // move the smaller element into a. while (iFirst < first.length && iSecond < second.length) { if (first[iFirst] < second[iSecond]) { a[j] = first[iFirst]; iFirst++; } else { a[j] = second[iSecond]; iSecond++; } j++; } // Note that only one of the two loops below copies entries. // Copy any remaining entries of the first array. while (iFirst < first.length) { a[j] = first[iFirst]; iFirst++; j++; } // Copy any remaining entries of the second half while (iSecond < second.length) { a[j] = second[iSecond]; iSecond++; j++; } } }