CSC 241- Set #7

Merge Sort

Mergesort is a divide and conquer method of sorting. It works by partitioning the list into two halfs, then applying merge sort to each half. This process continues until sublists contain a single element. The actual sorting occurs by a merge process that merges sublists as they return sorted. Although, mergeSort can be used in sorting arrays, lets consider it in the context of a linked list implementation.

The Algorithm has the following recursive structure:

Node mergeSort (Node head, int size) {
   if head is null or size 1
      return head
   else {
      create left and right sublists      
      left = mergeSort(left, leftSize)
      right = mergeSort(right,rightSize)
      return merge(left,right)
   }
}

Keep in mind that this is just an algorithm, you can't just type it in and expect it work. There are a number things that may not be obvious to to you:

1. Whenever there is more than one element in the list, the first job at hand is to break the list up into two halfs. Of course, we might not have an even number of elements which means one of the sublists will be longer than the other by one element. At this stage, the list being partitioned literally gets broken into two sublists. The size parameter is useful in locating the center and determining the size of each half. We then need to locate the node that should be at the end of the first half, keeping track of where the second sublist starts, and cutting their connection. Here is an example to illustrate:
   

         head --> 11 --> 9 --> 13 --> 10 --> 12 -->
               After splitting:
         first --> 11 --> 9 -->             second --> 13 --> 10 --> 12 -->
         

   Note that head will still be referencing the node with 11, but we don't care.

2. You should ask yourself why do left and right appear twice when mergeSort is invoked recursively? left and right references may change when mergeSort is called to sort their respective sublists. In Java, parameters can't change, so, you always return the reference to the beginning of the sorted list and store it back in the reference variable that used to refer to the beginning of the list; This is a typical technique for implementing recursive algorithms that manipulate lists.

3. merge is expected to combine the two sublists and return a list with all elements in a sorted order.

          mergeSort(head-->11-->9-->13-->10-->12 , size=5)
                 {return -->9-->10-->11-->12-->13}
                               /     \
                              /       \
mergeSort(head-->11-->9,size=2)        mergeSort(head-->13-->10-->12,size=3)
     {return -->9-->11-->}                  {return -->10-->12-->13-->}
                  /  \                                  /    \
                 /    \                                /      \
mergeSort(head-->11,  mergeSort(head-->9,             /        \
          size =1)              size =1)             /          \
  {return -->11}        {return -->9}               /            \
                                 mergeSort(head-->13, mergeSort(head-->10-->12,
                                           size =1)             size =2) 
                                      {return -->13}       {return -->10-->12}
                                                        /   \
                                                       /     \
                                                      /       \
                                                     /         \
                                  mergeSort(head-->10,  mergeSort(head-->12,
                                            size =1)              size =1) 
                                      {return -->10}       {return -->12}

Merging Sorted lists

Merging sorted lists requires an algorithm that considers each element of each list and ensures they appear in the correct sequence in the new list. The algorithms may be slightly different depending on the choice of data structure. Here we assume a linked list implementation:

    Make a list "newlist".

    Move the node with the smaller of the two values at the beginning of
    "first" or "second" into the new list.  Note, the node chosen here should
    no longer be in either first or second (i.e. first=first.next or
    second=second.next)


    Establish a reference variable "temp" to this first node on "newlist"
    

    while (first !=null && second != null) {
       append the node with the smaller of the two values at the
       beginning "first" and "second" to "newlist", removing it from
       its original sublist.  "temp" needs to keep track of the end
       of "newlist" where nodes are appended.
     }

     if (first !=null) append the rest of first to "newlist"
     if (second !=null) append the rest of second to "newlist"

Lets trace the algorithm:

Consider the 1st list containing: 12 16 17 20 21 27
Consider the 2nd list containing: 9 10 11 12 19

Here is how we perceive the two lists:

12 ---> 16 ---> 17 ---> 20 ---> 21 ---> 27
first

9 --->  10 ---> 11 ---> 12 ---> 19
second

before we begin the loop, newlist and temp are established, and we end up with
the following:

   12 ---> 16 ---> 17 ---> 20 ---> 21 ---> 27
   first

   10 ---> 11 ---> 12 ---> 19
   second

   9
   newlist & temp

After the First pass through the loop:


   12 ---> 16 ---> 17 ---> 20 ---> 21 ---> 27
   first

   11 ---> 12 ---> 19
   second

   9 --->  10
   newlist temp

Second pass:

   12 ---> 16 ---> 17 ---> 20 ---> 21 ---> 27
   first

   12 ---> 19
   second

   9 --->  10 ---> 11
   newlist         temp

Third pass:    Note that since first and second elements being
               considered are the same, it doesn't matter which is
               picked.


   12 ---> 16 ---> 17 ---> 20 ---> 21 ---> 27
   first

   19
   second

   9 --->  10 ---> 11 ---> 12
   newlist                 temp

Fourth pass:

   16 ---> 17 ---> 20 ---> 21 ---> 27
   first

   19
   second

   9 --->  10 ---> 11 ---> 12 ---> 12
   newlist                         temp

Fifth pass:

   17 ---> 20 ---> 21 ---> 27
   first

   19
   second

   9 --->  10 ---> 11 ---> 12 ---> 12 ---> 16
   newlist                                 temp

Sixth pass:

   20 ---> 21 ---> 27
   first

   19
   second

   9 --->  10 ---> 11 ---> 12 ---> 12 ---> 16 ---> 17
   newlist                                         temp 

Seventh pass: Note that once this cycle is finished the while loop condition
              no longer holds.

   20 ---> 21 ---> 27
   first

   (empty)
   second

   9 --->  10 ---> 11 ---> 12 ---> 12 ---> 16 ---> 17 ---> 19
   newlist                                                 temp

After the loop, since first is not null:

   9 --->  10 ---> 11 ---> 12 ---> 12 ---> 16 ---> 17 ---> 20 ---> 21 ---> 27
   newlist                                         temp

Since second is null, the next if statement fails, and newlist is
the result of the merger:


   9 --->  10 ---> 11 ---> 12 ---> 12 ---> 16 ---> 17 ---> 20 ---> 21 ---> 27
   newlist