Функция принимает два отсортированных от меньшего к большему

private static void merge(ArrayList<Integer> a, ArrayList<Integer> b) {
        int size = a.size();
        ArrayList<Integer> temp = new ArrayList<>(size * 2);
        int firstIdx = 0;
        int secondIdx = 0;
        for (; firstIdx < size && secondIdx < size; ) {
            temp.add(
                    a.get(firstIdx) < b.get(secondIdx) ? a.get(firstIdx++) : b.get(secondIdx++)
            );
        }

        ArrayList<Integer> last;
        int lastIdx;

        if (firstIdx < size) {
            last = a;
            lastIdx = firstIdx;
        } else {
            last = b;
            lastIdx = secondIdx;
        }

        for (int i = lastIdx; i < last.size(); i++) {
            temp.add(last.get(i));
        }
        a.clear();
        a.addAll(temp);
    }

В условии специально указано что эффективность важна. Как слить массивы максимально быстро и в минимальной памяти?

Минимальность по памяти достигается следующей конструкцией:

a.ensureCapacity(a.size() + b.size());
// a.addAll(b);
for (int l = 0; l < b.size(); ++l) {
    a.add(null);
}

ensureCapacity убеждается что в списке a достаточно места чтобы он мог быть увеличен до финального размера без выделения новой памяти. Без этого вызова массив a может быть перенесён в памяти несколько раз.

Цикл ниже растягивает список до окончательного размера. Вместо цикла можно вызвать a.addAll(b). Я этого не делаю чтобы было ясно что добавленные значения не важны.

Дальше сливаем списки с конца к началу. Из индексов i и j читаем, в k пишем:

           i        k                     j
           |        |                     |
a = [1, 3, 5, ?, ?, ?]         b = [2, 6, 8]

Сравниваем a[i] и b[j]. Больший присваиваем a[k]. Передвигаем индексы j и k:

           i     k                     j
           |     |                     |
a = [1, 3, 5, ?, ?, 8]         b = [2, 6, 8]

Ещё раз:

           i  k                     j
           |  |                     |
a = [1, 3, 5, ?, 6, 8]         b = [2, 6, 8]

Теперь a[i] > b[j]. Копируем из a[i] в a[k] и двигаем индексы i и k:

        i  k                        j
        |  |                        |
a = [1, 3, 5, 5, 6, 8]         b = [2, 6, 8]

Ещё раз:

     i  k                           j
     |  |                           |
a = [1, 3, 3, 5, 6, 8]         b = [2, 6, 8]

И ещё раз. Список b исчерпан. Можно прекращать работу:

    i,k
     |
a = [1, 2, 5, 5, 6, 8]         b = [2, 6, 8]

Возможна ситуация когда первым будет исчерпан список a, тогда надо докопировать значения, которые остались в b.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MergeSortedArrayListsInPlace {
    public static void main(String... args) {
        ArrayList<Integer> a = new ArrayList<Integer>(Arrays.asList(1, 3, 5));
        List<Integer> b = Arrays.asList(2, 6, 8);
        System.out.println(a);
        System.out.println(b);
        merge(a, b);
        System.out.println(a);
    }

    public static void merge(ArrayList<Integer> a, List<Integer> b) {
        int i = a.size() - 1; // читает из a, движется к нулю
        a.ensureCapacity(a.size() + b.size());
        // a.addAll(b);
        for (int l = 0; l < b.size(); ++l) {
            a.add(null);
        }
        int j = b.size() - 1; // читает из b, движется к нулю
        int k = a.size() - 1; // пишет в a, движется к нулю

        // слияние от больших к меньшим
        while (i >= 0 && j >= 0) {
            Integer av = a.get(i);
            Integer bv = b.get(j);
            if (av > bv) {
                a.set(k, av);
                --i;
            } else {
                a.set(k, bv);
                --j;
            }
            --k;
        }

        // копирование хвоста из b в a
        while (j >= 0) {
            a.set(k, b.get(j));
            --j;
            --k;
        }
    }
}

$ javac MergeSortedArrayListsInPlace.java && java MergeSortedArrayListsInPlace 
[1, 3, 5]
[2, 6, 8]
[1, 2, 3, 5, 6, 8]

Однако данный вариант кода не обрабатывает числа отрицательные. Сделал обработку и отрицательных.

public static void main(String[] args) {
        ArrayList<Integer> firstArray = new ArrayList<Integer>(Arrays.asList(-8, 22));
        List<Integer> secondArray = Arrays.asList(-5, 15);
        merge(firstArray, secondArray);
        System.out.println(firstArray);
        System.out.println(secondArray);
    }

    public static void merge(ArrayList<Integer> firstArray, List<Integer> secondArray) {
        int i = firstArray.size() - 1;
        int j = secondArray.size() - 1;
        firstArray.ensureCapacity(firstArray.size() + secondArray.size());
        for (int l = 0; l < secondArray.size(); ++l) {
            firstArray.add(null);
        }
        int k = firstArray.size() - 1;

        while (i >= 0 && j >= 0) {
            Integer firstArrayElement = firstArray.get(i);
            Integer secondArrayElement = secondArray.get(j);
            if (firstArrayElement > secondArrayElement) {
                firstArray.set(k, firstArrayElement);
                --i;
            } else {
                firstArray.set(k, secondArrayElement);
                --j;
            }
            --k;
            if (i < 0){
                firstArray.set(k, secondArrayElement);
            }  if (j == 1 && i == -1){
                firstArray.set(k-1, secondArray.get(k-1));
            }
        }
    }