算法系列<归并排序>

归并两个已排序的数组序列，归并之后的数组序列还是有序的

用java实现如下：

    /**
     * 归并排序:归并两个已排序(升序)的数组,归并之后是已排序的
     * 最好时间复杂度:O(N),最坏时间复杂度:O(NlogN),平均时间复杂度:O(NlogN),空间复杂度:O(N)
     * 测试case:
     * {},{}
     * {},{1,2,3}
     * {1,2,3},{}
     * {1,2,3},{4,5,6}
     * {4,5,6},{1,2,3}
     * {12,34,45},{3,8,96}
     * @param table1 已升序排序的数组1
     * @param table2 已升序排序的数组2
     * @return
     */

    public static int[] mergeSort(int[] table1,int[] table2){
        if(table1.length>0||table2.length>0) {
            int[] table = new int[table1.length + table2.length];
            for (int index = 0, i = 0, j = 0; index < table.length; index++) {
                if (i >= table1.length) {
                    table[index++] = table2[j++];
                } else if (j >= table2.length) {
                    table[index++] = table1[i++];
                } else if (table1[i] < table2[j]) {
                    table[index] = table1[i];
                    i++;
                } else {
                    table[index] = table2[j];
                    j++;

                }
            }
            return table;
        }else{
            return null;
        }
    }