package com.jiucaiyuan.net.algrithm.sort;



/**

 * 归并法排序

 *  思路：递归处理把数组分成左右两部分，左侧部分排成有序数组，右侧排成有序数组，然后再merge两个数组

 *

 * 算法时间复杂度是O(N*logN)  空间复杂度O(N)

 *

 *

 * Created by jiucaiyuan on 2022/3/5.

 */

public class ReduceMergeSort {

    public static void sort(int[] arr,int l,int r){

        if(l == r){

            return;

        }

        int mid = l + ((r-l)>>1);

        System.out.println("l="+l+"\tmid="+mid+"\tr="+r);

        sort(arr,l,mid);

        sort(arr,mid+1,r);

        merge(arr,l,mid,r);

    }

    /*

     * 合并arr[l,mid] 和 arr[mid+1,r] 两个数组

     */

    private static void merge(int[] arr, int l, int mid, int r) {

        System.out.println("l="+l+"\tmid="+mid+"\tr="+r);

        //合并后的数组

        int[] temp = new int[r - l +1];

        int i=0;

        int p1 = l;

        int p2 = mid + 1;

        //两个数组都有数时

        while(p1<=mid && p2<=r){

            temp[i++] = arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];

        }

        //前半段数组长

        while(p1<=mid){

            temp[i++] = arr[p1++];

        }

        //后半段数组长

        while(p2<=r){

            temp[i++] = arr[p2++];

        }

        //把合并后的temp数组复制到arr中

        for(int index=0;index<temp.length;index++){

            arr[l + index] = temp[index];

        }

    }

    public static void main(String[] args){

        int[] arr = {12,5,3,7,3,8,4,3,2,2,6,8,6,0,9,5,3};

        print(arr);

        sort(arr,0,arr.length-1);

        print(arr);

    }

    private static void print(int[] arr) {

        if(arr == null ){

            return;

        }

        for(int a : arr){

            System.out.print(a+"\t");

        }

        System.out.println();

    }

}