# Thread: iterative merge sort

1. Member
Join Date
Jan 2011
Location
Beirut, Lebanon
Posts
90
Rep Power
0

## 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

2. ## 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

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

## 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 :)

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

## Re: iterative merge sort

And to answer e is the index of the last element in the array :)

5. ## Re: iterative merge sort

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

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

## 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.

#### Posting Permissions

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