Skip to main content
Lesson 25 - Merge and Mergesort
Lesson MenuPreviousNext
  
A Non-Recursive Mergesort page 3 of 9

  1. The overall logic of mergesort is to "divide and conquer." A list of random integers will be split into two equal-sized lists (each with the same number of elements, plus or minus one), with each partial list or "sublist" sorted independently of the other. The next step will be to merge the two sorted sublists back into one sorted list.

  2. Here is a non-recursive mergeSort method. We divide the list into two equal-sized parts and sort each with the selection sort, then merge the two using an algorithm to be discussed in part B.

    /* List A is unsorted, with A.length values in the array.
       first is the index position of the first value; last
       is the index position of the last value in the array;
       first < last.
       */
    void mergeSort (int A[], int first, int last)
    {
      int  mid;
    
      mid = (first + last) / 2;
      selectionSort (A, first, mid);
      selectionSort (A, mid+1, last);
      merge (A, first, mid, last);
    }
  3. A modified selection sort would have to be written to sort a range of values in list A. Likewise, the merge method will also have to be modified to internally merge two halves of the array into one ordered array.

  4. The following example will illustrate the action of a non-recursive mergesort on a list of 8 values:

  5. Merging the two halves of the array in the modified merge method will require the use of a local temporary array. Because the two sublists are stored within one array, the easiest approach is to merge the two sublists into another array, then copy the temp array back to the original.

    Then copy Temp back into List A:

  6. This version of merge will need to be able to work with sections of List A. Here is a proposed method parameter list for merge:

    /* will merge the two sorted sublists within A into
       one continuous sublist from A[first] .. A[last].
       The left list ranges from A[first]..A[mid].  The
       right list ranges from A[mid+1]..A[last].
     */
    void merge (int A[], int first, int mid, int last)
  7. You will need to write the code for this version of the merge method to support a recursive mergesort. To assist you in that task, we next present a non-recursive mergesort algorithm.


Lesson MenuPreviousNext
Contact
 ©ICT 2003, All Rights Reserved.