9 Replies Latest reply: Mar 13, 2009 12:18 PM by 843785 RSS

    Merge Sort Algorithm

    843785
      Hi, i'm trying to write merge sort methods but I have 2 problems, here's the mergesort method, and then the merge method below where I have some problems:
      public static void mergesort(int[] array, int first, int last)
      {
         if (last-first > 1)
         {
            int mid = (first + last)/2;
            mergesort(array, first, mid); //recursive call 1
            mergesort(array, mid, last); //recusive call 2
            merge(array, first, mid, last);
         }
      }
      public static void merge(int[] array, int first, int mid, int last) {
           //merge array[first to mid-1] and array[mid to last-1]
           int leftpos = first;
           int rightpos = mid;
           int newpos = 0;
           int[] temparray = new int[x];//<------- What should the size of x be?
           while(leftpos<mid && rightpos<=(last-1)) {
                if (array[leftpos] <= array[rightpos]) {
                     temparray[newpos] = array[leftpos];
                     leftpos++; newpos++;
                }
           else {
                temparray[newpos] = array[rightpos];
                rightpos++; newpos++;
           }
           while(leftpos<mid){   //copy the rest of left half
                temparray[newpos] = array[leftpos];
                leftpos++; newpos++;
           }
           while(rightpos<=last-1) {   //copy the rest of right half (
                temparray[newpos] = array[rightpos];
                rightpos++; newpos++;
           }
      //          copy temparray to array[first to (last-1)]   <---- how do I do this?
           }
      }
      Any help?

      Thank you.
        • 1. Re: Merge Sort Algorithm
          699554
          Would you think it be useful to us if you explained what freakin problems your having
          • 2. Re: Merge Sort Algorithm
            843785
            Melanie_Green wrote:
            Would you think it be useful to us if you explained what freakin problems your having
            Probably freakin out because it is due today.
            • 3. Re: Merge Sort Algorithm
              843785
              Melanie_Green wrote:
              Would you think it be useful to us if you explained what freakin problems your having
              The two freaking problems are marked in the OP supplied code.
              • 4. Re: Merge Sort Algorithm
                843785
                lol yeah maybe I should have been more clear.. but the 2 problems I am having are commented in the second method.
                • 5. Re: Merge Sort Algorithm
                  843785
                  coldfire- wrote:
                  Hi, i'm trying to write merge sort methods
                  Because sorting algorithms are so thouroughly analysed and because the internet is full of Java implementations I feel helping you with debugging details is kind of wasted effort. To learn something you should do the debugging. If you want a working implementation just take your pick from the internet smorgasbord.
                  • 6. Re: Merge Sort Algorithm
                    843785
                    Seems you're trying to combine the "divide" step with the "conquer" step in the merge. I recently wrote a merge sort for one of my applications for alphabetizing. I followed Wikipedia's pseudocode and it was a piece of cake.

                    If you're using ArrayList (like I did) for the dividing, don't use remove(0) to shave the first item off after you're done with it in the loop(s) like the pseudocode seems to suggest because that causes all the indexes to shift. I cut a full 2 seconds off (down to 0 seconds) of a 75k word list sort by using ints as counters to go through the lists.

                    http://en.wikipedia.org/wiki/Merge_sort#Algorithm

                    Edited by: kavon89 on Mar 12, 2009 9:51 PM
                    • 7. Re: Merge Sort Algorithm
                      843785
                      kavon89 wrote:
                      Seems you're trying to combine the "divide" step with the "conquer" step in the merge. I recently wrote a merge sort for one of my applications for alphabetizing. I followed Wikipedia's pseudocode and it was a piece of cake.

                      If you're using ArrayList (like I did) for the dividing, don't use remove(0) to shave the first item off after you're done with it in the loop(s) like the pseudocode seems to suggest because that causes all the indexes to shift. I cut a full 2 seconds off (down to 0 seconds) of a 75k word list sort by using ints as counters to go through the lists.

                      http://en.wikipedia.org/wiki/Merge_sort#Algorithm

                      Edited by: kavon89 on Mar 12, 2009 9:51 PM
                      I was able to get my merge sort to work, but with the wordlist i'm using (150,000+ words) it is considerably slow! How does your algorithm compare with a word list of that size?
                      • 8. Re: Merge Sort Algorithm
                        843785
                        kavon89, i'm trying to write the methods from the pseudocode on that Wikipedia website. I wrote the mergesort method (hope it's right):
                        public ArrayList<String> merge_sort(ArrayList<String> m) {
                             ArrayList<String> left = new ArrayList<String>(); 
                             ArrayList<String> right = new ArrayList<String>(); 
                             ArrayList<String> result = new ArrayList<String>();
                            if (m.size() <= 1)
                                 return m;
                            else {
                                 // This calculation is for 1-based arrays. For 0-based, use length(m)/2 - 1.
                                 int middle = m.size() / 2;
                                 for(int x = 0; x < middle; x++)
                                      left.add(m.get(x));
                                 for(int y = middle; y < m.size(); y++)
                                      right.add(m.get(y));
                                 left = merge_sort(left);
                                 right = merge_sort(right);
                                 result = merge(left, right);
                                 return result;
                            }
                        }
                        But now I am having trouble writing the merge method, from this pseudocode:
                        function merge(left,right)
                            var list result
                            while length(left) > 0 and length(right) > 0
                                if first(left) &#8804; first(right)
                                    append first(left) to result
                                    left = rest(left)
                                else
                                    append first(right) to result
                                    right = rest(right)
                            end while
                            while length(left) > 0 
                                append left to result
                            while length(right) > 0 
                                append right to result
                            return result
                        I have:
                        public ArrayList<String> merge(ArrayList<String> left,ArrayList<String> right) {
                            ArrayList<String> result;
                            while(left.size() > 0 && right.size() > 0) {
                            .....
                        so far.. not really sure how to write the rest from that pseudocode. Perhaps you can give me some pointers?
                        • 9. Re: Merge Sort Algorithm
                          843785
                          I've added some comments to the psudocode of the merge.
                          function merge(left,right)
                              var list result //this is the list which be added to
                              while length(left) > 0 and length(right) > 0 
                                  if first(left)  first(right) //if the item in the "left" list is smaller than the right
                                      append first(left) to result //add the left one to the result (decending order)
                                      left = rest(left) //then remove it, or rather advance your index for the left side's list
                                  else
                                      append first(right) to result //otherwise obviously do the same as the above but for the right list
                                      right = rest(right)
                              end while 
                          
                          //now one of the lists has emptied up, time to add the leftovers which are already in order
                          
                              while length(left) > 0 
                                  append left to result
                              while length(right) > 0 
                                  append right to result
                              return result
                          Edited by: kavon89 on Mar 13, 2009 1:18 PM