/*
 * 递归之归并排序 
 * 归并排序就是将两个有序的数组，合到一起，得到一个新的有序数组的过程
 * 算法分析：首先拿a的第一个元素跟b的第一个元素比较，a的大，那么把b的元素放到新的数组c上
 * 然后再拿a的第一个元素跟b的第二个元素比较，a的元素小，那么就把a的第一个元素放到数组c上
 * 依次类推：当组数a的所有元素都被放到c中时，可以直接把b中剩下的元素直接放到c中，反之同理
 */
public class RecursiveMerge {

    public static void main(String[] args) {
        
        int[] a = {3,5,7,9,18,20,25,28,30,54,67,87,98};
        int[] b = {2,4,6,7,9,12,15,17,19,23,26,67};
        int[] c = new int[a.length + b.length];
        merge(a, b, c);
        for(int cv : c){
            System.out.print(cv +",");
        }
    }
    
    private static void merge(int[] a, int[] b, int[] c){
        int ai = 0; int bi = 0; int ci = 0;
        //当数组a或者数组b中有一个数组的数据已经被merge完了的时候，退出循环
        while(ai < a.length && bi < b.length){
            if(a[ai] > b[bi]){
                c[ci++] = b[bi++];
            }else{
                c[ci++] = a[ai++];
            }
        }
        //如果是b数组merge完了，那么把a数组剩下的元素放进去
        while(ai < a.length){
            c[ci++] = a[ai++];
        }
        //如果是a数组merge完了，那么把b数组剩下的元素放进去
        while(bi < b.length){
            c[ci++] = b[bi++];
        }
    }

}
 

//运行结果如下：

2,3,4,5,6,7,7,9,9,12,15,17,18,19,20,23,25,26,28,30,54,67,67,87,98,