TRAKLA2

Apply recursive mergesort to the following Input array. Hint: Draw a Call Tree for the recursive algorithm (see Insructions).

Some additional problems.

Merging is supposed to happend by drag & dropping items into Aixiliary Table. Use the corresponding indices in both arrays. Press Move button to copy an area from Auxiliary Table back to the original table. Note that in line 2, the division is truncated.

Example Call Tree for MERGESORT

Each node in Call Tree is split into two:
- Left side: parameter array Input[left,right]
- Right side: array Input[left,right] after a recursive call.


Example: Sorting array of size 4 with items 6,9,7,1. 
First call: MERGESORT(Input, 0, 3). 
Two recursive calls end in binary call tree.

          6971:1679
         /    \
      69:69  71:17
     / \    / \ 
   6:6 9:9 7:7 1:1

In which order Call Trees are traversed during recursion? Compare MERGESORT with the corresponding (recursive) tree traversal algorithm.