# My iterative merge sort

• Consider how iterative merge sort works. first time merge 2 elements, then 4 elements, then 8 elements, until all elements.

Use two lists to represent all odd merge parts and all even merge parts.

At first, convert the list to two lists:

top : 1st 3rd 5th 7th ...

bottom : 2nd 4th 6th 8th ...

then merge sort, first time:

top : SortResult(1st, 2nd) | SortResult(5th, 6th) ...

bottom : SortResult(3rd, 4th) | SortResult(7th, 8th) ...

second time:

top : SortResult(1st, 2nd, 3rd, 4th) ...

bottom : SortResult(5th, 6th, 7th, 8th) ...

Actually, if we have previous sort result:

top : s(1) s(3) ...

bottom : s(2) s(4) ...

we can sort it to get:

top : sort(s(1), s(2)) ...

bottom : sort(s(3), s(4)) ...

The code is below:

``````public class Solution
{
private ListNode merge(ListNode dest, ListNode src, int step)
{
int destCount = 0;
int srcCount = 0;
final int max = step >>> 1;
for (int j = 0; j < step; ++j)
{
if (dest.next == null || destCount >= max)
{
if (src.next == null)
{
break;
}
else
{
final ListNode temp = dest.next;
dest.next = src.next;
src.next = src.next.next;
dest = dest.next;
dest.next = temp;
}
}
else if (src.next == null || srcCount >= max)
{
if (dest.next != null)
{
dest = dest.next;
}
}
else
{
if (dest.next.val <= src.next.val)
{
dest = dest.next;
++destCount;
}
else
{
final ListNode temp = dest.next;
dest.next = src.next;
src.next = src.next.next;
dest = dest.next;
dest.next = temp;
++srcCount;
}
}
}

return dest;
}

{
{
}

final ListNode topHead = new ListNode(0);
final ListNode bottomHead = new ListNode(0);

for (; node != null && node.next != null; node = node.next)
{
top.next = node;
top = top.next;

node = node.next;

bottom.next = node;
bottom = bottom.next;
}

top.next = node;
bottom.next = null;

for (int i = 1; bottomHead.next != null; i <<= 1)
{

while (top.next != null && bottom.next != null)
{
top = merge(top, bottom, i << 1);
bottom = merge(bottom, top, i << 1);
}
}