class ArrayMerger {

    private int[] aux;
    private int[] array;

    private int leftArrayIndex;
    private int rightArrayIndex;
    private int arrayIndex;

    private int leftSubArrayEnd;
    private int rightSubArrayEnd;

    public ArrayMerger(int[] array) {
        this.array = array;
        this.aux = new int[array.length];
    }

    private void prepareToMerge(int low, int mid, int high) {
        this.arrayIndex = low;
        this.leftArrayIndex = low;
        this.rightArrayIndex = mid;
        this.leftSubArrayEnd = mid;
        this.rightSubArrayEnd = high;
        System.arraycopy(array, low, aux, low, high - low);
    }

    public void merge(int low, int mid, int high) {
        prepareToMerge(low, mid, high);
        while (hasValuesToMerge()) {
            if (isRightSubArrayEmpty()) {
                takeValueFromLeftSubArray();
            } else if (isLeftSubArrayEmpty()) {
                takeValueFromRightSubArray();
            } else if (isValueInLeftArraySmaller()) {
                takeValueFromLeftSubArray();
            } else {
                takeValueFromRightSubArray();
            }
        }
    }

    private boolean isValueInLeftArraySmaller() {
        return aux[leftArrayIndex] < aux[rightArrayIndex];
    }

    private void takeValueFromLeftSubArray() {
        array[arrayIndex++] = aux[leftArrayIndex++];
    }

    private void takeValueFromRightSubArray() {
        array[arrayIndex++] = aux[rightArrayIndex++];
    }

    private boolean isRightSubArrayEmpty() {
        return rightArrayIndex >= rightSubArrayEnd;
    }

    private boolean isLeftSubArrayEmpty() {
        return leftArrayIndex >= leftSubArrayEnd;
    }

    private boolean hasValuesToMerge() {
        return leftArrayIndex < leftSubArrayEnd || rightArrayIndex < rightSubArrayEnd;
    }

}