//MERGESORTimport java.util.*;public class MergeSorter{ //mergesort subarray from [start,end) end exclusive public static void mergesort(int[] array, int start, int end) { System.out.println("Sorting subarray (" + start +" to "+end+")"); 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); mergesort(array,start+size/2,end); 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) { System.out.print("Merging ("+a+", "+b+", "+c+") of "); printArray(arr); 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++]; System.out.print(" Merged sub-array: "); printArray(tmp); } 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); mergesort(array,0,array.length); System.out.print("Output: "); printArray(array); } public static void printArray(int[] array) { System.out.print("["); for (int i : array) System.out.print(i+" "); System.out.println("]"); }}