MergeSort


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 2 of 2

Thread: MergeSort

  1. #1
    Join Date
    Dec 2005
    Posts
    27

    MergeSort

    I am having trouble writing a mergesort.
    Here is the alogorithm that i need to use
    Code:
     
    # /**
    * recursive mergesort of an array of integers
    *
    * @param a reference to an array of integers to be sorted
    * @param first starting index of range of values to be sorted
    * @param last ending index of range of values to be sorted
    */
    void recursiveMergeSort (int [ ] a, int first, int last)
    // Recursively divides a list in half, over and over. When the
    // sublist has one or two values, stop subdividing.
    {
       if (sublist has only one value)
          do nothing
       else if (sublist has two values)
          sort it if necessary
       else // recursion, divide list into two halves
          Find midpoint of current sublist
          Call recursiveMergeSort and process left sublist
          Call recursiveMergeSort and process right sublist
          merge left and right sublists
    }
    # You will also have to write the code for method:
    
    private void merge (int [ ] a, int first, int mid, int last)
    {
       // Replace this line with your code
    }
    Here is what i have so far.

    Code:
     
    public void mergeSort(int a[], int first, int last)  
        {        
            if(last > first)
            {
                return; 
            }
            else if(a[last] == a[first +1])
            {
                for(int i = 0; i <= a.length -1 ; i ++)
                {
                    if(a[i] > a[i+1])
                    {
                        int temp = a[i]; 
                        a[i] = a[i+1]; 
                        a[i+1] = temp; 
                    }
                }
            }
            else
            {
                int mid = (first + last)/2; 
                mergeSort(a, first, mid);
                mergeSort(a, mid, last); 
                
            }
        }

  2. #2
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    You're missing the whole "take 'em apart and put them back together again" which is the basis of the merge sort - THERE IS NO SWAPPING INVOLVED.

    You recursively break down the parts, by two, until they are single, then you stitch the parts back together into larger and larger parts, merging them so they are in "order"

    16->(2-8's)->(4-4's)->(8-2's)->(16-1's)
    then
    (16-1's)->(8-2's)->(4-4's)->(2-8's)->1-16

    when you are down to 1, you take each pair of runs and decide - which of the elements which is "first" in each run is the "less than the other"? That is the one which gets merged back into the larger run first. When that is moved, then compare which is "first" again, and copy that. Keep going until you've depleted both runs - there is a trick here - you'll have three conditions: both sub arrays have elements, only the "left" array has elements, only the "right" array has elements ... and then you have completed the merge back in.

    For your recursive procedure, you will be performing an "in place" merge sort, ultimately writing back into your original array. The procedure will take your array - parent -, break it into two parts - child 1, child 2, break out child1 into grandchild 1 and 2, then grandchild 1 into greatgrandchild 1 and 2, until you are down to a pair of decendant arrays of length 1. Then write back the lesser of each, into its parent array, and continue on up, until you have returned to your original array.

    Since you are using arrays rather than lists, you will need some help in handling the arrays. Keep the System.arraycopy method in mind to create your child arrays. Also, you will have to iterate yourself through the child arrays while you are merging back - you don't want to delete and rewrite, etc. - pretty messy. So you'll need to keep track of where you are in each array. Do you know how to create and use an iterator in the array? This also allows you to test whether the array has anything left, using the iterator's hasNext() method. If not, you can approximate the action of an iterator by increasing the index of the array in question until you have reached the length of the array.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center