package algorithm.sort; import java.util.Random; /** *
* Merge Sort is a Divide and Conquer sorting algorithm. *
* * Divide Step : * Divide the current array into two halves and then recursively sort the two halves. * * Conquer Step : * Merge the two (sorted) halves to form a sorted array. */ public class MergeSort { public static void main(String[] args) { int problemSize = 15; final Random random = new Random(); // int[] data = new int[]{29,62,28,78,83,91,96,64,27,64}; int[] data = new int[problemSize]; for(int i = 0; i < problemSize; i ++) { data[i] = random.nextInt(150); System.out.println(data[i]); } mergeSort(data, 0, data.length - 1); System.out.println(" -- Sorted --"); for(int i = 0; i < problemSize; i ++) { System.out.println(data[i]); } } /** * * * @param array * @param low * @param high */ public static void mergeSort(int array[], int low, int high) { if (low < high) { // ½áÊøÌõ¼þ£¬·Ö½âµ½Ö»ÓÐÒ»¸öÔªËØ int mid = (low+high) / 2; mergeSort(array, low , mid ); // divide into two halves mergeSort(array, mid+1, high); // then recursively sort them merge(array, low, mid, high); // conquer: the merge routine } } /** * Եغϲ¢Êý×éµÄ×óÓÒÁ½²¿·Ö¡£ * Ñ»·±éÀúÁ½¸ö²¿·Ö£¬Í¨¹ý±È½ÏheadÔªËØ£¬ÊµÏֺϲ¢¡£ * ´úÂëÖÐÒÀÀµcopy¿Õ¼äÀ´ÁÙʱ´æ·ÅÅÅÐòºóµÄ½á¹û¡£ * @param array * @param low * @param mid * @param high */ public static void merge(int[] array, int low, int mid, int high) { int n = high - low + 1; int leftHead = low; int rightHead = mid + 1; int[] copy = new int[n]; int idx = 0; while( leftHead <= mid && rightHead <= high ) { if( array[leftHead] <= array[rightHead]) { copy[idx++] = array[leftHead++]; } else { copy[idx++] = array[rightHead++]; } } while(leftHead <= mid) { copy[idx++] = array[leftHead++]; } while(rightHead <= high) { copy[idx++] = array[rightHead++]; } for(int k = 0; k < n; k++) { array[low + k] = copy[k]; } } }