package algorithm.sort;


import java.util.Random;


/**
 * <p>
 * Merge Sort is a Divide and Conquer sorting algorithm.
 * </p>
 *
 * 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];
        }
    }
}