My iterative merge sort


  • 5
    L

    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;
        }
        
        public ListNode sortList(ListNode head)
        {
            if (head == null || head.next == null)
            {
                return head;
            }
            
            final ListNode topHead = new ListNode(0);
            final ListNode bottomHead = new ListNode(0);
            
            ListNode top = topHead;
            ListNode bottom = bottomHead;
            
            ListNode node = head;
            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)
            {
                top = topHead;
                bottom = bottomHead;
                
                while (top.next != null && bottom.next != null)
                {
                    top = merge(top, bottom, i << 1);
                    bottom = merge(bottom, top, i << 1);
                }
            }
            
            return topHead.next;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.