8.7 Linked-List Implementations of Mergesort

---

Extra space appears to be required for a practical implementation of mergesort, so we may as well consider a linked-list implementation. In other words, rather than use the extra space for an auxiliary array, we can use it for links. We can build a general-purpose sort along these lines, or we might well be presented with the problem of sorting a linked list in the first place (see Section 6.9). In fact, mergesort turns out to be well-suited to linked lists. A full implementation of the merge method for linked lists is given in Program 8.6. Note that the code for the actual merge is just about as simple as the code for array-based merge (Program 8.2).

Given this merge method, a top-down mergesort is easy to derive. Program 8.7 is a direct recursive implementation of a method that takes as input a reference to an unordered list and returns a reference to a list comprising the same elements, in sorted order. The program does its work by rearranging the nodes of the list: No temporary nodes or lists need to be allocated. Program 8.7 uses a trick to find the middle of the list: alternative implementations might do so either by passing the list length as a parameter to the recursive program or by storing the length with the list. This program is simple to understand in a recursive formulation, even though it is a sophisticated algorithm.

Program 8.6 Linked-list merge

This program merges the list referenced by a with the list referenced by b, with the help of an auxiliary reference variable c. The key comparison in merge includes equality, so that the merge will be stable, if the b list is considered to follow the a list. For simplicity, we adopt the convention that all lists end with 0. Other conventions for ending the list would work as well (see Table 3.1). More important, we do not use list head nodes, in order to avoid proliferation of them.

 static Node merge(Node a, Node b)    { Node dummy = new Node();      Node head = dummy, c = head;      while ((a != null) && (b != null))        if (less(a.item, b.item))          { c.next = a; c = a; a = a.next; }        else          { c.next = b; c = b; b = b.next; }      c.next = (a == null) ? b : a;      return head.next;    } 

We can also use a bottom-up combine-and-conquer approach for linked-list mergesort, although details of keeping track of links make this implementation more challenging than it might seem. As we discussed when considering bottom-up array-based methods in Section 8.5, there is no particular reason to adhere precisely to the set of merges performed by the recursive or array-based versions when we are developing a bottom-up list mergesort.

An amusing version of bottom-up linked-list mergesort suggests itself that is simple to explain: Put the items in a circular list, then proceed through the list, merging together pairs of ordered subfiles until done. This method is conceptually simple, but (as with most low-level programs involving linked lists) it can be tricky to implement (see Exercise 8.36). Another version of bottom-up linked-list mergesort that is based on the same idea is given in Program 8.8: keep all the lists to be merged on a queue ADT. This method is also conceptually simple, but (as with many high-level programs involving ADTs) it can also be tricky to implement. But it does offer an excellent example of the use of an ADT abstraction to support a higher-level computation.

Program 8.7 Top-down list mergesort

This program sorts by splitting the list referenced by c into two halves referenced by a and b, sorting the two halves recursively, and then using merge (Program 8.6) to produce the final result. The input list must end with null (and therefore so does the b list), and the explicit instruction c.next = null puts null at the end of the a list.

 static Node mergesort(Node c)    {      if (c == null || c.next == null) return c;      Node a = c, b = c.next;      while ((b != null) && (b.next != null))        { c = c.next; b = (b.next).next; }      b = c.next; c.next = null;      return merge(mergesort(a), mergesort(b));    } 

One important feature of this method is that it method takes advantage of any order that might be already present in the file. Indeed, the number of passes through the list is not lg N , but rather is lg S , where S is the number of ordered subfiles in the original array. Mergesorts with this property are sometimes called natural mergesorts. For random files, natural mergesorts offer no great advantage, because only a pass or two is likely to be saved (in fact, the method is likely to be slower than the top-down method, because of the extra cost of checking for order in the file), but it is not uncommon for a file to consist of blocks of ordered subfiles, and this method will be effective in such situations.

Program 8.8 Bottom-up list mergesort

This program uses a queue ADT (Program 4.18) to implement a bottom-up mergesort. Queue elements are ordered linked lists. After initializing the queue with lists of length 1, the program simply removes two lists from the queue, merges them, and puts the result back on the queue, continuing until there is only one list. This corresponds to a sequence of passes through all the elements, doubling the length of the ordered lists on each pass, as in bottom-up mergesort.

 static Node mergesort(Node t)    {      NodeQueue Q = new NodeQueue();      if (t == null || t.next == null) return t;      for (Node u = null; t != null; t = u)        { u = t.next; t.next = null; Q.put(t); }      t = Q.get();      while (!Q.empty())        { Q.put(t); t = merge(Q.get(), Q.get()); }      return t;    } 

Exercises

8.33 Develop an implementation of top-down list mergesort that carries the list length as a parameter to the recursive procedure and uses it to determine how to split the lists.

8.34 Develop an implementation of top-down list mergesort that works with lists that carry their length in header nodes and uses the lengths to determine how to split the lists.

8.35 Add a cutoff for small subfiles to Program 8.7. Determine the extent to which proper choice of the cutoff value speeds up the program.

8.37 Add a cutoff for small subfiles to your bottom-up circular-list mergesort from Exercise 8.36. Determine the extent to which proper choice of the cutoff value speeds up the program.

8.38 Add a cutoff for small subfiles to Program 8.8. Determine the extent to which proper choice of the cutoff value speeds up the program.

N = 16, 24, 31, 32, 33, and 39.

8.40 Draw combine-and-conquer trees that summarize the merges that circular-list mergesort (Exercise 8.38) performs, for N = 16, 24, 31, 32, 33, and 39.

8.41 Run empirical studies to develop a hypothesis about the number of ordered subfiles in an array of N random 32-bit integers.

8.42 Empirically determine the number of passes needed in a natural mergesort for random 64-bit keys with N = 10³, 10⁴, 10⁵, and 10⁶. Hint: You do not need to implement a sort (or even generate full 64-bit keys) to complete this exercise.

8.43 Convert Program 8.8 into a natural mergesort, by initially populating the queue with the ordered subfiles that occur in the input.

Top