# iterative merge sort

• 10-23-2011, 09:23 PM
baf06
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
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 :(blush): :(angel):
• 10-23-2011, 09:42 PM
JosAH
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
• 10-23-2011, 09:56 PM
baf06
Re: iterative merge sort
thanks alot josAH :(blush):
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
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 :)
• 10-23-2011, 09:59 PM
baf06
Re: iterative merge sort
And to answer e is the index of the last element in the array :)
• 10-23-2011, 10:01 PM
JosAH
Re: iterative merge sort
Quote:

Originally Posted by baf06
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
• 10-23-2011, 10:17 PM
baf06
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.