//MERGESORTimport java.util.*;public class MergeSorter{ public static int depth=0; //mergesort subarray from [start,end) end exclusive public static void mergesort(int[] array, int start, int end) { depth++; printDepth(' '); System.out.print("Sorting subarray from " + start +" to "+end+": "); printArray(array,start,end); System.out.println(); int size=end-start; switch (size) { case 2: testAndSwap(array,start,start+1); case 1: //fallthrough return; } //split&merge mergesort(array,start,start+size/2); depth--; mergesort(array,start+size/2,end); depth--; merge(array,start,start+size/2,end); } //switch 2 numbers if not in order public static void testAndSwap(int[] a, int f, int s) { if (a[f] < a[s]) return; int tmp=a[f]; a[f]=a[s]; a[s]=tmp; } //merge 2 sub-arrays a - inclusive, c - exclusive public static void merge(int[] arr, int a, int b, int c) { printDepth(' '); System.out.print("Merging "); printArray(arr,a,b); System.out.print(" and "); printArray(arr,b,c); System.out.println(); int x=a, y=b, tmp[] = new int[c-a], z=0; //sort fill temp till 1 subarray is empty while (x < b && y < c) if (arr[x] > arr[y]) tmp[z++]=arr[y++]; else tmp[z++]=arr[x++]; //fill remainder while (x < b) tmp[z++]=arr[x++]; while (y < c) tmp[z++]=arr[y++]; //copy back z=0; for (int i=a;i<c;i++) arr[i]=tmp[z++]; printDepth(' '); System.out.print(" Merged sub-array: "); printArray(tmp,0,tmp.length); System.out.println(); } public static void main(String args[]) { int[] array=new int[13]; //initialize random numbers Random r = new Random(); for (int i=0;i<array.length;i++) array[i]=r.nextInt(100); System.out.print("Input: "); printArray(array,0,array.length); System.out.println(); mergesort(array,0,array.length); System.out.print("Output: "); printArray(array,0,array.length); System.out.println(); } public static void printArray(int[] array,int start, int end) { System.out.print("["); for (int i=start;i<end;i++) System.out.print(array[i]+" "); System.out.print("]"); } public static void printDepth(char c) { for(int i=0;i<depth;i++) System.out.print(c); }}