# Short and clean python quick sort solution.

• The ticky is dividing the list into three part in every scan loop. Left part is less than pivot, middle part is equals to pivot, and right part is greater than pivot.

``````# requirement: hat is not None
def quick_sort(hat, tail):
if hat.next is tail or hat.next.next is tail:
return

hat1, hat2, hat3 = hat, hat.next, ListNode(None)
tail1, tail2, tail3 = hat1, hat2, hat3
p, pivot = hat2.next, hat2.val
while p is not tail:
if p.val < pivot:
tail1.next, tail1, p = p, p, p.next
elif p.val == pivot:
tail2.next, tail2, p = p, p, p.next
else:
tail3.next, tail3, p = p, p, p.next

# Caution: DO NOT change the order of these three line codes below.
tail3.next = tail
tail2.next = hat3.next
tail1.next = hat2

quick_sort(hat1, hat2)
quick_sort(tail2, tail)

class Solution:
# @return {ListNode}
hat = ListNode(None)
quick_sort(hat, None)
return hat.next``````

• I have a question, is recursive solution considered `constant space complexity'? Cause the stack will use O(nlogn) space if it is called recursively.

• Hi, JinhongChen. You are right, this solution can not be considered "constant space complexity". Since it is recursive, the stack will use O(log(n)) space.
By the way, could anyone find a constant space complexity and a O(n*log(n)) time complexity solution for this problem?

• Use iterative method then. But I do favor writing recursive solution for quick-sort or merge-sort problems

• I think the iterative method can't be considered "constant space complexity" too. Because it uses a manual stack.

• Hi, MissMary. Mergesort solution would have constant space complexity since we don't need to use extra storage for "merge". I've implemented it as following:

1. Start from the head of the list (let it be n1)
2. Follow the pointers from n1 to find the next node with smaller value than the previous (let it be n2)
3. Call merge with n1 and n2. Merge will proceed until we processed all elements from n1 to n2 and encountered the value smaller than the previous one in the sequence starting with n2. Return the node with that smaller value and use it as new n1. Remember the fact that you called merge.
4. Repeat until you reach the end of the list.
5. Check if you called merge during this run. If not, the array is sorted, otherwise - reset n1 to head and repeat.

Step 5 might be optimized a bit to avoid an extra pass in some cases.

• Hi, freevoid. This is really a good idea. Thank you very much. Would you provide your AC code?

• Sure, here it is:

``````class Solution(object):
"""
:rtype: ListNode
"""

node_prev = None
merges_in_pass = 0
while True:
node2_prev = node
if node:
node2 = node.next
else:
node2 = None

while node2 and node2.val >= node2_prev.val:
node2_prev = node2
node2 = node2.next

if node2 is not None:
assert node2_prev is not None
merges_in_pass += 1
else:
if merges_in_pass > 1 or (merges_in_pass == 1 and node is not None):
node_prev = None
merges_in_pass = 0
else:

def merge(n1, n2, n1_prev, n2_prev, head):
if n2 is None:

while n1 != n2 and n2 is not None:
if n1.val <= n2.val:
n1_prev = n1
n1 = n1.next
else:
next_n2 = n2.next
n2_prev.next = next_n2
if n1_prev is None:
else:
n1_prev.next = n2
n2.next = n1
n1_prev = n2

if next_n2 and n2.val > next_n2.val:
n2 = next_n2
break
else:
n2 = next_n2

while n2 and n2.val >= n2_prev.val:
n2_prev = n2
n2 = n2.next