Results 1 to 6 of 6
  1. #1
    baf06 is offline Member
    Join Date
    Jan 2011
    Location
    Beirut, Lebanon
    Posts
    90
    Rep Power
    0

    Lightbulb iterative merge sort

    hello everyone,
    hope you are having a good weekend :)
    I am working on an algorithm problem, I wrote a psuedo code for iterative merge sort and transferred it to a java code, Iterative merge code is the non-recursive version of mergeSort, every thing is working perfectly but the annoying problem is that when I try my code on an odd-array I just neglects the last element and keep it in place even if it is the smallest value.
    This is my code
    Java Code:
    public static void main(String[] args){
            int[] list = {4, 7, 1, 8, 9, 2, 0, 3, 10, 17, 5, 20, 5};
            
            mergeSort(list, 0 , list.length-1);
            
            System.out.println(Arrays.toString(list));
        }
    
        private static void mergeSort(int[] list, int s, int e){
            int m = 1;              //counts the level, depending on number of elements in each sublist, 1-2-4-8...
            int end = 0;            //variable to be used to determine the last sublist depending on length of list
            while ( m < e){         //while not reached the final list
                int count = 0;
                int i = 0;
                while (i < e-m ){   //while we can divide the original array into subarrays of m elements
                    if(count == list.length/(m*2))
                        end = e-1;
                    else end = i+2*m-1;
                    merge(list, i, i+m-1 , end);    //merge the sublist of m elements from s to end
                    i = i + 2*m;                    //increment i by 2*m
                    count++;
                }
                m = m * 2;          //double the m to apply 2-4-8...
            }
        }
    and this is the result I got: [0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 17, 20, 5]
    I didn't post the merge method since i am sure that it is correct, I tried having many condition before the start of the merging but none worked. So hope someone knows any trick :)
    appreciate any help
    Click on REP and add to member reputation, if you find their advices/solutions effective.

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,560
    Blog Entries
    7
    Rep Power
    21

    Default Re: iterative merge sort

    My guess is that it depends on the value of parameter 'e' in your mergeSort( ... ) method. Is it supposed to be the index of the last element in your list or is it supposed to point one element beyond the last element? Depending on that you have to check lines #4 and #12.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    baf06 is offline Member
    Join Date
    Jan 2011
    Location
    Beirut, Lebanon
    Posts
    90
    Rep Power
    0

    Default Re: iterative merge sort

    thanks alot josAH
    I tried this but it didn't change any result values, but just had an idea that may not be considered efficient but here is the code
    Java Code:
            if(list.length%2 == 1){         //if the length of the list is odd merge the last element with the even sorted array before it
                merge(list, s, e-1, e);
            }
    I added this code at the end of my mergeSort method, but just notice a problem after testing the code on a bigger array,
    of 32 elements for example, but it didn't change the last element, since it is not divisible by 4. Am working on this right now, but any idea may help :)
    Click on REP and add to member reputation, if you find their advices/solutions effective.

  4. #4
    baf06 is offline Member
    Join Date
    Jan 2011
    Location
    Beirut, Lebanon
    Posts
    90
    Rep Power
    0

    Default Re: iterative merge sort

    And to answer e is the index of the last element in the array :)
    Click on REP and add to member reputation, if you find their advices/solutions effective.

  5. #5
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,560
    Blog Entries
    7
    Rep Power
    21

    Default Re: iterative merge sort

    Quote Originally Posted by baf06 View Post
    And to answer e is the index of the last element in the array :)
    Shouldn't line #12 read: "while (m <= e)" then?

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  6. #6
    baf06 is offline Member
    Join Date
    Jan 2011
    Location
    Beirut, Lebanon
    Posts
    90
    Rep Power
    0

    Default Re: iterative merge sort

    yes it should, I changed it. but the new problem is not solvable with and if statement, since it can be not divisible by 4, or by 8 or 16 ...
    so what can be done in this case ? although I googled this code and none had any condition regarding this problem.
    Click on REP and add to member reputation, if you find their advices/solutions effective.

Similar Threads

  1. merge sort with recursive method (need help badlly!!)
    By zetalore in forum Advanced Java
    Replies: 0
    Last Post: 01-08-2011, 07:10 PM
  2. Iterative help
    By Jnoobs in forum New To Java
    Replies: 5
    Last Post: 10-06-2010, 08:26 PM
  3. Using Merge Sort to sort an ArrayList of Strings
    By coldfire in forum New To Java
    Replies: 3
    Last Post: 03-13-2009, 01:03 AM
  4. Merge Sort in Java
    By Java Tip in forum Algorithms
    Replies: 0
    Last Post: 04-15-2008, 07:43 PM
  5. Merge Sort Help
    By Hollywood in forum New To Java
    Replies: 5
    Last Post: 01-30-2008, 03:26 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •