# Assignment 12 - Alternative Mergesort Implementation

1. Getting Started.

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.

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.
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.