Почему функция Merge Sort's Merge() имеет условный второй цикл?

Question

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) 
    } 
} 

Итак, в основном, это на моих лекциях. В целом я нахожу это довольно запутанным, но я понимаю большую его часть. То, что я не понимаю, - это необходимость части «if (j < = low + k - 1)». Похоже, он проверяет, есть ли в левой части какие-либо элементы «слева». Это возможно даже при слиянии?

Answer 1

При объединении двух отсортированных списков (назовем их left и right), вы продолжаете принимать один пункт и добавить его в список result, пока вы бежите из элементов в любом списке left или right. Это делается с помощью первого цикла while. Теперь вам нужно добавить элементы, оставшиеся в левом или правом списке, в список результатов. Существует два варианта:

• В левом списке нет элементов, а в правом списке все еще есть. Как здесь написано код, нам ничего не нужно делать, поскольку в конце массива S уже содержатся последние элементы в списке right.

• Правый список не содержит элементов, а в левом списке все еще есть. Затем мы копируем оставшиеся элементы в конец S. Это то, что делает if в конце merge1.

---

Что касается вашего вопроса, если этот код «плохо»: код правильный, но я хотел бы сделать некоторые изменения, чтобы сделать его более удобным для чтения:

• Описательные имена переменных.
• Передача промежуточной точки, которая отделяет left и right списков до merge1 вместо того, чтобы она пересчитывала.