Merge Sort with Lists

The reading on the merge sort discussed an approach for sorting an array by successively merging small ordered arrays to get larger ordered arrays. The basic approach followed these steps:

• Start with ordered arrays of size 1 (note: any array of size 1 is ordered), and merge these arrays of size 1 to get ordered arrays of size 2.
• Merge the arrays of size 2 to get arrays of size 4.
• Merge the arrays of size 4 to get arrays of size 8.
• Etc.

When using arrays, we could access each array element immediately; we did not have to start at position 0 in the array and move element by element to get the n^th item. Further, we could keep track of bounds of array segments in loops as part of the merge process. Pragmatically, we worked from array segments of size 1 and processed larger pieces as the algorithm progressed

Although we used iteration in the algorithm, recursion works just as well (perhaps more simply). The basic approach for a recursive algorithm starts with the large collection of data and recursive relies on calls to sort smaller collections: This approach is outlined as follows:

• Start with a collection of n elements
  • if n is 0 or 1, the collection is sorted.
  • if n > 1,
    • Divide the collection of n elements into two pieces of half the size (subcollection1 and subcollection2).
    • Recursively sort subcollection1 and subcollection2.
    • Merge subcollections1 and subcollection2 to obtain a full collection of size n (the sorted version of the original collection).

In code, this outline might proceed as follows when sorting items within a list of ListNode elements:

  public ListNode mergeSortLists (ListNode ls) {
     /* handle base cases */
     if ((ls == null) || (ls.getNext () == null)
        {
          return ls;
        }
     /* divide ls into two pieces of approximately equal size*/
     ListNode sublist1 = ...
     ListNode sublist2 = ...

     /* sort both sublists*/
     sublist1 = mergeSortLists (sublist1);
     sublist2 = mergeSortLists (sublist2);

     /* merge the two lists to get the sorted result */
     return listMerge (sublist1, sublist2);
  }  

With this code outlined, the work remaining involves

1. dividing a list into two pieces of approximately equal size.
2. merging two ordered lists into one.

Splitting a List into Two Pieces

This task can be handled in at least two ways, each of which requires a little care, but neither of which requires extensive coding.

• Counting:

  • First count the items on the list (perhaps getting a number numb).
  • Starting at the beginning of the list again, count nodes until reaching numb/2. At this point,
    • sublist2 can point to the next node.
    • The next field of node number numb/2 can be set to null.
    • sublist1 can now point to the first half of the original list.

  Overall with this approach, sublist1 references the first half of the list, and sublist2 references the second half of the list.

• Alternating assignments:

  • In going through the list, assign successive nodes, first to the end of sublist1 and then to the end of sublist2

  In following this approach, note that finding the end of a sublist can be time consuming, if one starts at the beginning each time. Thus, in this setting, we use sublist1 and sublist2 to keep track of the head of each created list, and separate variables can keep track of the tail of each list:

  

Merging Lists

The reading on the merge sort presented the following outline for merging two sorted collections:

• As long as items exist in both array segments:

  • examine the first item in each array segment, copy the smaller to the new array, and ignore the copied element in further processing.

• Copy any remaining elements from the first array segment to the new array.

• Copy any remaining elements from the second array segment to the new array.

Although work for this lab involves merging lists rather than arrays, the same outline applies—moving list nodes rather than array elements.

Work for this Lab

1. Create a mergeSortLists method within a list class, such as NameList, including the basic code structure identified above.

2. Use either the counting or alternating assignments method to split a list into two pieces of approximately equal size.

3. Write a method ListNode mergeSortLists (ListNode sublist1, ListNode sublist2) that follows the above outline to merge ordered two lists into one.

Note that completing the above three steps should yield a complete merge sort for lists!

4. Add some testing to your list class, so this merge sort algorithm can be tested appropriately.

created 1 February 2020 revised 2 February 2020
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.