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
UNTIL HERE in the last line have to be replaced. The following should
jpoint to the current places in the lists to be merged,
kto the place in the merged list.
second[j]values should be compared.
i, j, kvariables 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
One sorted list is
second[lowerbound] … second[middlebound-1],
the other sorted list is
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.