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)
}
}
I am really sorry for the terrible formating, as you can tell I am not a regular visitor here.
So, basically, this is on my lecture notes. I find it quite confusing in general but I understand the biggest part of it. What I don't understand is the need of the "if (j <= low + k - 1)" part. It looks like it checks if there are any elements "left" in the left part. Is that even possible when mergesorting?
