Lab 6: Merge sort; a first look at linked lists

Task 1: Practice merge sort
Task 2: Work with a linked list of characters
Task 3: Understand assignments involving references
Task 4: Show us your work

FLR 267

If your lab meets in FLR 267, you should begin by following the instructions found here.

Task 1: Practice merge sort

Your work for this lab should go on the piece of paper that we give you. Please show your paper to a staff member before you leave the lab.

Like quicksort, merge sort uses a recursive, divide-and-conquer approach. However, whereas quicksort does all of its work during the divide stage (before making the recursive calls), merge sort instead does all of its work after a given set of recursive calls have returned, as it merges sorted subarrays.

Let’s trace through mergesort on the following array:

                  -----------------------------------------
                  |  7 | 39 | 20 | 11 | 16 |  5 |  9 | 28 |
                  -----------------------------------------
                                    split
                              /               \
              ---------------------       ---------------------
              |    |    |    |    |       |    |    |    |    |
              ---------------------       ---------------------
                    split                           split
                /           \                   /           \
        -----------     -----------       -----------     -----------
        |    |    |     |    |    |       |    |    |     |    |    |
        -----------     -----------       -----------     -----------
      split               split               split               split
    /       \           /       \           /       \           /       \
 ------   ------     ------   ------     ------   ------     ------   ------
 |    |   |    |     |    |   |    |     |    |   |    |     |    |   |    |
 ------   ------     ------   ------     ------   ------     ------   ------
    \       /           \       /           \       /           \       /
      merge               merge               merge               merge
   -----------         -----------         -----------         -----------
   |    |    |         |    |    |         |    |    |         |    |    |
   -----------         -----------         -----------         -----------
             \         /                             \         /
                merge                                   merge  
        ---------------------                   ---------------------
        |    |    |    |    |                   |    |    |    |    |
        ---------------------                   ---------------------
                  \                                       /
                  -----------------------------------------
                  |    |    |    |    |    |    |    |    |
                  -----------------------------------------

What major advantage does merge sort have over quicksort with respect to time complexity?
What major disadvantage does merge sort have compared to quicksort with respect to space complexity?

Task 2: Work with a linked list of characters

In lecture, we’ve been considering linked lists of characters, where each node in the linked list is an instance of the following class:

public class StringNode {
    private char ch;
    private StringNode next;
    ...
}

For example, we considered the following linked list, which represents the string "dog":

Note that each node in the linked list has two fields:

the top field (the field ch), which stores a single character
the bottom field (the field next), which is a reference of type StringNode. These next fields link the nodes together. They either hold a reference to the next node in the linked list, or (in the case of the last node) they have a value of null to indicate that there are no subsequent nodes.

Your tasks

Consider the following diagram, which is a visualization of a heap memory region in which a number of StringNode objects have been created. Each node includes the values of its ch and next fields, as well its starting position in memory.
```
     0xc000            0xbe00            0x3004
     +--------+        +--------+        +--------+
  ch |   'a'  |     ch |   'b'  |     ch |   'c'  |
     +--------+        +--------+        +--------+
next | 0xbe00 |   next | 0x3004 |   next | 0xbb00 |
     +--------+        +--------+        +--------+

     0xa004            0xff00            0xbb00
     +--------+        +--------+        +--------+
  ch |   'd'  |     ch |   'e'  |     ch |   'f'  |
     +--------+        +--------+        +--------+
next | 0xff00 |   next |  null  |   next | 0xa004 |
     +--------+        +--------+        +--------+
```
Important notes:
- Instead of using arrows to represent each node’s next field, we have written the actual value of each reference (or null, in the case of no reference). We have written these reference values as hexadecimal (base 16) numbers that begin with 0x.
- The order of the nodes in the diagram does not necessarily correspond to the order of the nodes in the linked list. This is also true when you create a linked list in your program. The nodes are not necessarily next to each other in memory. They can be located at arbitrary locations on the heap. That is why each node must maintain a reference to the next node!
Convert the diagram above to one that looks like the diagrams from lecture, in which:
- the nodes are shown in a single chain stretching from the first node to the last node in the linked list
- references are drawn using arrows
Your new diagram should still include the memory address of the start of each node.

Note: The node containing the letter 'a' is the first node in the linked list. To determine the order of the remaining nodes, follow the next references!
Suppose that we have two variables in the main method of our StringNode class:
- one called n, which holds a reference to the node at address 0xbe00
- one called m, which holds a reference to the node at address 0xbb00
Add the variables n and m to the diagram you created for question 2.
In the rest of this task, we will determine both the address and the value of several fields from our diagram.

To do so, we will make the following assumptions:
- the memory address of the ch field of a StringNode is the same as the address of the StringNode itself
- the memory address of the next field of a StringNode is 2 more than the address of the StringNode itself.
Complete the table shown below, filling in the address and value of the field specified by each expression from the left-hand column. We have done the first two expressions for you.
```
expression         address        value
----------         -------        -----
m.ch               0xbb00         'f'
m.next             0xbb02         0xa004 (reference to the 'd' node)
m.next.next
n.next
n.next.ch
n.next.next.next
```

Task 3: Understand assignments involving references

To determine the effect of an assignment statement involving references, it can help to use the following procedure:

Identify the two boxes – i.e., the variables/fields specified by the expressions on both sides of the assignment operator.
Determine the value in the box specified by the expression on the right-hand side.
Copy that value into the box specified by the expression on the left-hand side.

Beginning with our diagram from Task 2:

Draw the diagram that results from the following assignment:
```
n = m.next;
```
Now modify the drawing to show the result of the following:
```
m.next = m.next.next
```

Task 4: Show us your work

You should show the paper with your work to the teaching assistant.

Don’t worry if you didn’t finish all of the tasks. You should just show us whatever work you were able to complete during lab.