История изменений
Исправление victor79, (текущая версия) :
В любом случае сложность O(N1+N2) + аллокация. Именно «примитивным» слиянием это и делается.
вставка одного в упорядоченный будет O(log(N) + аллокация)
можно модифицировать исходный массив
Можно. Это возвращаемый результат из рекурсии, в рекурсию же, и дальше рекурсивно складывается, удаляя уже сложенное.
в значительном проценте случаев все ключи меньшего массива уже есть в большем
Верно, нюансов достаточно.
Исправление victor79, :
В любом случае сложность O(N1+N2) + аллокация. Именно «примитивным» слиянием это и делается.
вставка одного в упорядоченный будет O(log(N) + аллокация)
можно модифицировать исходный массив
Можно. Это возвращаемый результат из рекурсии, в рекурсию же, и дальше рекурсивно складывается, удаляя уже сложенное.
начительном проценте случаев все ключи меньшего массива уже есть в большем
Верно, нюансов достаточно.
Исправление victor79, :
В любом случае сложность O(N1+N2) + аллокация. Именно «примитивным» слиянием это и делается.
вставка одного в упорядоченный будет O(log(N) + аллокация)
можно модифицировать исходный массив
Можно. Это возвращаемый результат из рекурсии, в рекурсию же, и дальше рекурсивно складывается, удаляя уже сложенное.
Исходная версия victor79, :
В любом случае сложность O(N1+N2) + аллокация. Именно «примитивным» слиянием это и делается.
вставка одного в упорядоченный будет O(log(N) + аллокация)