Алгоритм сортировки слиянием
Шаг 1 — если это только один элемент в списке, он уже отсортирован, возврат. Шаг 2 — рекурсивно разделите список на две половины, пока его больше нельзя будет разделить. Шаг 3 — объедините меньшие списки в новый список в отсортированном порядке.
с этим псевдокодом:
procedure mergesort( var a as array )
if ( n == 1 ) return a
var l1 as array = a[0] ... a[n/2]
var l2 as array = a[n/2+1] ... a[n]
l1 = mergesort( l1 )
l2 = mergesort( l2 )
return merge( l1, l2 )
end procedure
procedure merge( var a as array, var b as array )
var c as array
while ( a and b have elements )
if ( a[0] > b[0] )
add b[0] to the end of c
remove b[0] from b
else
add a[0] to the end of c
remove a[0] from a
end if
end while
while ( a has elements )
add a[0] to the end of c
remove a[0] from a
end while
while ( b has elements )
add b[0] to the end of c
remove b[0] from b
end while
return c
end procedure
мой вопрос:
в функции merge есть два цикла while для проверки наличия элементов в a
и b
и добавления их в массив c
.
мой вопрос: будут ли (могут ли) эти два пока выполняться в одной и той же функции?
или например, если a
все еще есть элементы, это означает, что b
определенно пусто, и наоборот?