Сортированный массив массивов Вопрос

Question

Возможно ли, что два отсортированных списка размером n/2 могут быть объединены с использованием n/2 размера рабочего массива ???

Answer 1

Это не влияет на сложность O (n). Вы не можете получить n/2 все время. A = [1,2,3,10] B = [4,5,6,8]

Для этого вам нужно n-1.

Answer 2

Если вы имеете в виду рабочий массив, как в дополнительном хранилище, требуемом над финальным массивом, вам это даже не нужно. Чтобы отсортировать два списка, которые уже, вам нужно всего лишь объединить их, и для этого требуется только два значения (по одному в списке источников), а не n/2.

алгоритм выглядит следующим образом: «Вы можете объединить два n/2 -размер массива в другой массив n/2 -размер»

create empty list newlist 
set idx1 to start of list1 
set idx2 to start of list2 
while idx1 within list1 or idx2 within list2: 
    if idx1 beyond list1: 
     append list2[idx2] to newlist 
     increment idx2 
    else if idx2 beyond list2: 
     append list1[idx1] to newlist 
     increment idx1 
    else if list1[idx1] is less than list2[idx2]: 
     append list1[idx1] to newlist 
     increment idx1 
    else: 
     append list2[idx2] to newlist 
     increment idx2 

Если вы имеете в виду то, не выполняя некоторые обманки, где вы можете объединить два элемента в один (например, буксировать 16-битные целые числа в 32-битный элемент), нет, это невозможно.