используем библиотеку известных алгоритмов;
ход 1: соединяем оба массива в один в любом порядке;
ход 2: выполняем любую известную сортировку, например, быструю сортировку Хоара

коммент 1: хитрость в том, что два массива следует рассматривать как один неупорядоченный, тогда задача является обычной задачей на упорядочение массива
коммент 2: задача глупая, как и все "хитрые" задачи типа олимпиадных, потому что такие задачи ищут не собственно решение, а умение решателя проникнуть в мозги постановщика задачи: решатель должен не задачу решить, а найти, какую гадость задумал постановщик

нужно 3 индексных переменных допустим i j k соответственно для 1го 2го и результирующего массивов.
в цикле для k сравниваем элементы массивов и добавляем минимальный, а потом увеличиваем его индекс на единицу.

тупо

Ну просто применить процедуру merge из сортировки слиянием. (О(n1 + n2))
Создать сбалансированное дерево на основе одного из массивов и вставлять в него второй (O(n2 * lg n1))
Соединить и отсортировать (O(n lg n))

О(n1 + n2) - это правильная оценка. остальное - костыли и индийский код, извините.
аноним (26.05.10) был прав, но страшнее то, что 3 из 4х запаролись на тупой задаче, но знают сорт. Хоара.

1. выделить место под новый массив размера n1 + n2
2. поставить указатели(не буквально, достаточно целочисленных))) ) на элементы концов массивов, являющиемя минимальными в каждом из своих массивов(обобцаем задачу на случай разной упорядоченности)
3. из элементов под указателями берем минимальный. Записываем его зн. на новое место.
4. увеличиваем индекс рецепиента и выбранного донора
5. повторяем с пункта 3, пока не кончится один из доноров
6. дописываем в конец оставшиеся элементы (они уже упорядочены и заведомо больше всех вставленных ранее)
7. ....
8. Профит!!!

@DirectX:
Но это не сработает на массивах разной длины.
Если я верно понял идею, то (javascript) реализация нечто вроде:

var a1 = [2,4,6,10,12];
var a2 = [1,2,3,5,6,7,8,9];
var result = [];
var steps = a1.length + a2.length;
for(var i=0, j=0, k=0; k < steps; k++){
if(a1[i] < a2[j]){
result.push(a1[i]);
i++;
}
else {
result.push(a2[j]);
j++;
}
}
console.log(result);