1 package sorts; 2  3 import java.util.Arrays; 4 import java.util.Random; 5  6 public class MergeSort { 7  8     public static <T extends Comparable<T>> void sort(T[] array) { 9         T[] workspace = (T[])new Comparable[array.length]; // only 1 workspace is claimed, no more copies10         recMerge(array, 0, array.length-1, workspace);11     }12     13     /**14      * recursively merge15      * */16     private static <T extends Comparable<T>> void recMerge(T[] array,17             int lowerBound, int upperBound, T[] wp) {18         if (lowerBound == upperBound) {19             return;20         } else {21             int mid = ((lowerBound + upperBound)>>1); // (low + upper) / 222             recMerge(array, lowerBound, mid, wp);23             recMerge(array, mid+1, upperBound, wp);24             merge(array, lowerBound, mid, upperBound, wp);25         }26     }27     /**28      * Merge two sorted array into one.29      * */30     private static <T extends Comparable<T>> void merge(T[] array,31             int lowerBound, int mid, int upperBound, T[] wp) {32         int lowIndex = lowerBound;33         int highIndex = mid + 1;34         int j = 0; // workspace index35         // merge them into one array36         while (lowIndex <= mid && highIndex <= upperBound) {37             if (array[lowIndex].compareTo(array[highIndex]) < 0) {38                 wp[j++] = array[lowIndex++];39             } else {40                 wp[j++] = array[highIndex++];41             }42         }43         // copy the rest44         while (lowIndex <= mid) {45             wp[j++] = array[lowIndex++];46         }47         while (highIndex <= upperBound) {48             wp[j++] = array[highIndex++];49         }50         // copy the merged array into the original array51         int n = upperBound - lowerBound + 1;52         for (int i = 0; i < n; i++) {53             array[lowerBound+i] = wp[i];54         }55     }56     57     // test58     public static void main(String[] args) {59         Random random = new Random();60         int num = 10;61         int bound = 100;62         Integer[] a = new Integer[num];63         for (int i = 0; i < num; i++) {64             a[i] = random.nextInt(bound);65         }66         MergeSort.sort(a);67         System.out.println(Arrays.toString(a));68     }69 70 }