merge1(int low, int high, int S[], U[])
{
int k = (high - low + 1)/2
for q (from low to high) U[q] = S[q]
int j = low
int p = low
int i = low + k
while (j <= low + k - 1) and (i <= high) do
{
if ( U[j] <= U[i] )
{
S[p] := U[j]
j := j+1
}
else
{
S[p] := U[i]
i := i+1
}
p := p+1
}
if (j <= low + k - 1)
{
for q from p to high do
{
S[q] := U[j]
j := j+1
}
}
}
merge_sort1(int low, int high, int S[], U[])
{
if low < high
{
int k := (high - low + 1)/2
merge_sort1(low, low+k-1, S, U)
merge_sort1(low+k, high, S, U)
merge1(low, high, S, U)
}
}
Так, в основном это находится на моих нотах лекции. Я нахожу это довольно сбивающим с толку в целом, но я понимаю самую большую часть его. То, что я не понимаю, является потребностью "если (j <= низко + k - 1)" часть. Похоже, что это проверяет, существуют ли какие-либо элементы, "оставленные" в левой части. Это даже возможно при сортировке с объединением?
При объединении двух отсортированных списков (назовем их слева
и справа
), вы продолжаете брать один элемент и добавлять его в список результат
, пока вы не закончились элементы в левом
или правом
списке. Это выполняется первым циклом while
. Теперь вам нужно добавить элементы, оставшиеся в левом или правом списке, в список результатов. Есть два варианта:
В левом списке нет элементов, а в правом списке все еще есть. Так как здесь написан код, нам ничего делать не нужно, поскольку конец массива S
уже содержит последние элементы в списке справа
.
В правом списке нет элементов, а в левом списке все еще есть. Затем копируем оставшиеся элементы в конец S
. Это то, что делает if
в конце merge1
.
Относительно вашего вопроса, является ли этот код «плохим»: код правильный, но я бы внес некоторые изменения, чтобы сделать его более читабельным:
левый
и правый
списки, в merge1
вместо повторного вычисления.