Sorted List Array Question

Question

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

Answer 1

Если вы имеете в виду рабочий массив как в дополнительном хранилище, необходимом сверх конечного массива, вам это даже не нужно.Для сортировки двух списков, которые уже отсортированы, вам нужно только объединить их, для чего требуется только два значения (по одному на список источников) вместо 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

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

Answer 2

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

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