Please refer to this page for information on how to work on your assignment.
This implementation of Mergesort makes a heavy use of shift and push operations. This homework has the goal to implement the same algorithm with just accessing indices. Therefore, the data structures are easier, but one has to do more to keep track of the current positions than in the case of shifting and pushing data of arrays.
The algorithm is basically the same as in the implemented version for the lecture. But it is coded differently. Look at the source code to get a picture what is going on. Except of the merging step, everything is there.
The task is to implement the merge step on indices in the algorithm below.
The three lines with EDIT FROM HERE
in the first and EDIT
UNTIL HERE
in the last line have to be replaced. The following should
be done:
i
and j
point to the
current places in the lists to be merged, k
to the place
in the merged list.
second[i]
and second[j]
values should be
compared.
first[k]
.i, j, k
variables have to be updated accordingly, that
is the one giving the origin and the one giving the destination of the
moved number have to be increased by one. The third variable remains
unchanged.
Concerning the implemented part of the algorithm, it is useful to read this
explanation: the parts to be merged are in the second
array.
One sorted list is second[lowerbound] … second[middlebound-1]
,
the other sorted list is second[middlebound] …
second[upperbound-1]
. The target of the merge step is
first[lowerbound] … first[upperbound-1]
. The
count
variable is only there to count the number of
comparisons carried out by the algorithm. There should be exactly one
comparison in the loop to be programmed.