Как объединить два отсортированных массива?

Merge из merge sort. Два указателя i и j на начала массивов. Сравниваешь a[i] и b[j], меньший кладёшь в результат, сдвигаешь указатель. Когда один массив кончился — дописываешь остаток другого через append(result, a[i:]...). O(n+m) времени и памяти. Это фундаментальная операция — используется в merge sort, merge k sorted lists, external sort. На собесе важно не забыть обработку когда один массив пустой.