Как доказать правильность следующего алгоритма?

Рассмотрим следующий алгоритм min, который принимает списки x, y в качестве параметров и возвращает z-й наименьший элемент в объединении x и y. Предварительные условия: X и Y — отсортированные списки целых чисел в порядке возрастания, и они не пересекаются.

Обратите внимание, что это псевдокод, поэтому индексация начинается с 1, а не с 0.

Min(x,y,z):
    if z = 1:
        return(min(x[1]; y[1]))
    if z = 2:
        if x[1] < y[1]:
            return(min(x[2],y[1]))
        else:
            return(min(x[1], y[2]))

q = Ceiling(z/2) //round up z/2

if x[q] < y[z-q + 1]:
    return(Min(x[q:z], y[1:(z - q + 1)], (z-q +1)))
else:
    return(Min(x[1:q], B[(z -q + 1):z], q))

Я могу доказать, что оно обрывается, потому что z продолжает уменьшаться на 2 и в конце концов достигнет одного из базовых случаев, но я не могу доказать частичную правильность.