Assignment 12 - Alternative Mergesort Implementation

You can download this homework and set the permissions with the commands 
      cd ~/public_html
      wget http://www.comp.nus.edu.sg/~gem1501/assignment12.html
      chmod 755 *.html
Outline
There implementation of Mergesort makes heavily 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 then in the case of shifting and pushing data of arrays.

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.

Task
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 points and j point to the current places in the lists to be merged, k to the place in the merged list.
  2. The values second[i] and second[j] should be compared.
  3. The smaller one of them should go into first[k].
  4. The variables i,j,k 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.
Further Information
Concerning the implemented part of the algorithm, it is useful to read this explanations: The parts to be merged are in the array second. 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 variable count is there only to count the number of comparisons carried out by the algorithm. There should be exactly one comparison in the loop to be programmed.

Java Script starts here.

Java Script ends here.