Merging with smaller auxiliary a

Suppose that the subarray a[0] to a[n-1] is sorted and the subarray a[n] to a[2n-1] is sorted. How can you merge the two subarrays so that a[0] to a[2n-1] is sorted using an auxiliary array of length n (instead of 2n)

分析：

对两个大小分别为n的有序子数组进行归并，要求空间复杂度为n，正常情况下归并排序在此处的空间复杂度为2n，但是由于两个子数组分别是有序的，故用大小为n的额外子空间辅助归并是个很合理的要求，实现如下：

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));
    }
}