LeetCode Sort List Analysis: Bottom Up

Overview

The bottom up source code is given and several noteworthy details (e.g., pointer manipulation) on both the recursive and iterative merge sort are discussed.

leetcode Sort List Problem Description

Sort a linked list in O(n log n) time using constant space complexity.

leetcode Sort List Analysis

Among all the sorting algorithms, only Merge Sort, Quick Sort, Heap Sort come into my mind after I read the problem which requires O(NlogN) time complexity. Quick Sort cannot guarantee the worst time complexity O(NlogN), and at least to me, I could not find a good way to use a linked list to keep Heap structure. So Merge Sort come into place. The following is my accepted code (a bottom up merge sort approach), and I will comment on several noteworthy points after:

class Solution {
public:
	void Merge(ListNode *p1, ListNode *p2, ListNode **newHead, ListNode **newTail)
	{
		if (NULL == p1) {
			*newHead = *newTail = p2;
			while (p2) {
				p2 = p2->next;
				if (p2) *newTail = p2;
			}
			return ;
		}
		if (NULL == p2) {
			*newHead = *newTail = p1;
			while (p1) {
				p1 = p1->next;
				if (p1) *newTail = p1;
			}
			return ;
		}

		ListNode *head(NULL), *tail(NULL);

		ListNode **smaller = &p2;
		if (p1->val < p2->val) smaller = &p1;

		head = tail = *smaller;
		(*smaller) = (*smaller)->next;
		tail->next = NULL;

		while (p1 && p2) {
			smaller = &p2;
			if (p1->val < p2->val) smaller = &p1;

			tail->next = (*smaller);
			tail = tail->next;
			(*smaller) = (*smaller)->next;
			tail->next = NULL;
		}

		if (p1) tail->next = p1;
		if (p2) tail->next = p2;

		while (tail->next) tail = tail->next;

		*newHead = head;
		*newTail = tail;

		return ;
	}
	ListNode *MergeSortIterativelyBottonUp(ListNode *pListHead)
	{
		int len = 0;
		ListNode *pCurrentNode = pListHead;
		while (pCurrentNode) {++len; pCurrentNode = pCurrentNode->next; }

		ListNode *p1(pListHead), *p2(pListHead), *pNext(pListHead);
		ListNode *pNewHead(pListHead), *pNewTail(pListHead), *pTemp(pListHead);
		ListNode *pGlobalNewHead = pListHead;
		ListNode *pLastTail = pListHead;
		for (int step = 1; step < len; step *= 2) {
			pGlobalNewHead = NULL;
			while (pNext) {
				p1 = p2 = pNext;
				for (int j = 1; j < step && p2; ++j) pNext = p2 = p2->next;
				if (NULL == p2) break;

				pNext = p2->next;
				p2->next = NULL;
				p2 = pNext;
				for (int j = 1; j < step && pNext; ++j) pNext = pNext->next;

				if (pNext) {
					pTemp = pNext->next;
					pNext->next = NULL;
					pNext = pTemp;
				}

				pLastTail = pNewTail;
				Merge(p1, p2, &pNewHead, &pNewTail);
				if (NULL == pGlobalNewHead)
					pGlobalNewHead = pNewHead;
				else
					pLastTail->next = pNewHead;

				pNewTail->next = pNext;
			}
			pNext = pGlobalNewHead;
		}
		return pGlobalNewHead;
	}

	ListNode *sortList(ListNode *head) {
		return MergeSortIterativelyBottonUp(head);
    }
};

I have some further comments:

(1) You could find the detailed description of the bottom up merge sort on Wiki pages, but it utilize an auxiliary array to help. For the List implementation, it follows similar framework: the outer for loop just controls the size of each small list piece to merge, which the inner loop will go through the whole list to first cut, then merge and finally splice pieces of small lists.  The finally splice (i.e., connect separated lists) is important since it is not array you always need to keep the whole list structure complete and connected in order to do next round of Merge (outer for loop), and this is also the difficult point I think within this problem and make the implementation quite a bit error-prone with the pointer manipulation.

(2) Well, if you you search the internet, the recursive implementation of the Merge Sort is also quite popular, I also more like the recursive one because it is less error prone, I would recommend the recursive implementation if we are not required to use constant memory. I implement the recursive approach too but it does not meet the problem requirements so I don’t bother to show the code here. But if you want to try yourself, one of the important things is to split the list into two halfs, I have two ideas, the first is to use one pass to get the length of the list and do split quite similar to manipulating an array, the second is using slow/fast pointers with the fast pointer move 2 steps and the slow pointer moves 1 step at a time. The latter one is more natural regarding with Linked List operations. Additionally, the related problem “Merge Two Sorted List” also helps here, it is a better option to solve it first before really getting into the one in this current post.

(3) And as you could see from my code, it is a bit tedious, and my experience of implementing this code told me this is quite error-prone since it involves quite many pointer manipulations. So if any one could comment on my code and give some suggestions on how to further simply this bottom up implementation and make it less error-prone, it would highly appreciated!!! Thanks a lot!!!

leetcode Sort List Tips and Remarks:

Natural Merge Sort costs O(NlogN) time O(N) space

Recursive Merge Sort using Linked List costs O(NlogN) time and O(logN) space

Bottom up Merge Sort using Linked List costs O(NlogN) time and O(1) space

Open question: What about the natural Merge sort on arrays? Can it be done by using constant space, i.e., O(1) space? You might want to check my older post: “leetcode: Merge Sorted Array“.

Update about the open question found from coursera: It is possible to implement a linearithmic version of mergesort that  uses only logarithmic extra space (other than the input array), but such versions are not currently practical. That is,  the merging step can be done using only logarithmic (or even constant) extra space but no such method is known to be practical.

Summary

The bottom up source code is given and several noteworthy details (e.g., pointer manipulation) on both the recursive and iterative merge sort are discussed.

 


(Please specify the source  烟客旅人 sigmainfy — http://www.sigmainfy.com  as well as the original permalink

URL for any reprints,  and please do not use it for commercial purpose)

Written on July 29, 2014