Объединение двух отсортированных массивов в единый упорядоченный массив

Условие

Имеются два массива X и Y, отсортированных по возрастанию, их размеры — m и n соответственно. Требуется сформировать новый массив Z, содержащий все элементы массивов X и Y и упорядоченный также по возрастанию.

Ответ

Используйте два указателя: переносите меньший из текущих элементов, затем допишите оставшийся хвост. Сортировать объединённый массив заново не нужно.

Пример Go:

func mergeSorted(x, y []int) []int {
    result := make([]int, 0, len(x)+len(y))
    i, j := 0, 0
    for i < len(x) && j < len(y) {
        if x[i] <= y[j] {
            result = append(result, x[i]); i++
        } else {
            result = append(result, y[j]); j++
        }
    }
    result = append(result, x[i:]...)
    result = append(result, y[j:]...)
    return result
}

Время O(m+n), память O(m+n) для результата. Повторы сохраняются, пустые входы допустимы, исходные массивы не изменяются.