import java.util.Arrays;

 import edu.princeton.cs.algs4.StdRandom;

 public class MergeSortedSubArray {

     private static boolean less(Comparable v, Comparable w) {

         return v.compareTo(w) < 0;

     }

     public static void merge(Comparable[] array){

         int n = array.length/2;

         Comparable[] aux = new Comparable[n];

         for(int i=0;i<n;i++){ //取左半边sorted的元素至辅助数组，因为未来归并左侧位置可能会被右侧元素占据

             aux[i] = array[i];

         }

         System.out.println(Arrays.toString(aux));

         int l = 0;

         int r = n;

         for(int k = 0; k<2*n;k++){

             if(l >= n) break;//辅助元素数组全部用完，array右侧不需要挪动位置了

             else if(r>=2*n) array[k]=aux[l++];//array原右侧元素全部放置合适位置，后面只需把辅助数组的元素挪到array右侧

             else if(less(array[r],aux[l])) array[k] = array[r++];

             else array[k] = aux[l++];

         }

     }

     public static void main(String[] args){

         int n = 10;

         int[] subarray1 = new int[n];

         int[] subarray2 = new int[n];

         for (int i = 0; i < n; i++) {

             subarray1[i] = StdRandom.uniform(100);

             subarray2[i] = StdRandom.uniform(100);

         }

         Arrays.sort(subarray1);

         Arrays.sort(subarray2);

         Integer[] array = new Integer[2*n];

         for(int i = 0; i<n;i++){

             array[i] = subarray1[i];

             array[n+i] = subarray2[i];

         }

         System.out.println(Arrays.toString(array));

         merge(array);

         System.out.println(Arrays.toString(array));

     }

 }