public final class Merge { private static int [] temp; public static void merge_sort (int [] data, int n) { temp = new int [n]; // no use allocating it again and again merge_sort (data, 0, n); // sort the whole array } // Sort the elements data[first..first+n-1] public static void merge_sort (int [] data, int first, int n) { System.out.printf ("number=%d; range=%d..%d: ", n, first, first+n-1); System.out.println (java.util.Arrays.toString (data)); if (n>1) { System.out.printf ("first=%d, n=%d: ", first, n); printArray (data, first, n); final int n1 = n/2; final int n2 = n-n1; assert n1+n2==n; merge_sort (data, first, n1); // Sort data[first..first+n1-1] merge_sort (data, first+n1, n2); // Sort data[first+n1..first+n-1] System.out.print ("after both recursive calls: "); printArray (data, first, n); merge (data, first, n1, n2); System.out.print ("after merge "); printArray (data, first, n); } } /* Merge data[first..first+n1-1] and data[first+n1..first+n1+n2-1] */ public static void merge (int [] data, int first, int n1, int n2) { int copiedTotal=0, copiedLeft=0, copiedRight=0; while ((copiedLeft<n1) && (copiedRight<n2)) { if (data[first+copiedLeft]<data[first+n1+copiedRight]) { temp[copiedTotal++] = data[first + (copiedLeft++)]; } else { temp[copiedTotal++] = data[first + n1 + (copiedRight++)]; } } while (copiedLeft < n1) temp[copiedTotal++] = data[first+(copiedLeft++)]; while (copiedRight < n2) temp[copiedTotal++] = data[first+n1+(copiedRight++)]; assert copiedTotal == n1+n2; System.arraycopy (temp, 0, data, first, copiedTotal); } private static void printArray (int [] data, int n) { printArray (data, 0, n); } private static void printArray (int [] data, int first, int n) { System.out.print ("["); for (int i=first; i<first+n; i++) { System.out.print (data[i]); if (i<first+n-1) System.out.print (", "); } System.out.println ("]"); } public static void main (final String [] args) { final int [] data = new int [args.length]; int n = 0; for (int i=0; i<args.length; i++) { try { data[n++] = Integer.parseInt(args[i]); } catch (NumberFormatException ex) { // ignore bad input } } printArray (data, n); merge_sort (data, n); printArray (data, n); } }