Assignment 12 - Alternative Mergesort Implementation

1. Getting Started.

   Please refer to this page for information on how to work on your assignment.

2. Outline

   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.

3. Algorithm

   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.

4. Task of this exercise.

   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:

   1. There are three variables which point to the places currently considered: i and j point to the current places in the lists to be merged, k to the place in the merged list.
   2. The second[i] and second[j] values should be compared.
   3. The smaller one of them should go into first[k].
   4. The 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.
5. Further Information

   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.