CSC 241- Week 10 (April 2, 1997)

Merge Sort

Mergesort is yet another 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. I'll discuss the algorithm for merging sublists later.

          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}