# Sort List — Day 17(Python)

Today we will be visiting one of the questions from Leetcode’s daily coding challenge October edition.

148. Sort List

Given the `head` of a linked list, return the list after sorting it in ascending order.

Follow up: Can you sort the linked list in `O(n logn)` time and `O(1)` memory (i.e. constant space)?

Example 1:

`Input: head = [4,2,1,3]Output: [1,2,3,4]`

Example 2:

`Input: head = [-1,5,3,4,0]Output: [-1,0,3,4,5]`

Example 3:

`Input: head = []Output: []`

Constraints:

• The number of nodes in the list is in the range `[0, 5 * 104]`.
• `-105 <= Node.val <= 105`

To sort LinkedList, we usually use merge-sort. To understand why merge-sort, we need to understand the working of merge-sort.
Merge-sort, as the name suggests, is one of the sorting algorithms. It falls in the Divide and Conquer category of algorithms. The basic idea is to divide a given array into subarrays until such that just one element is present in the subarray. After division, we compare each subarray and merge them. Eventually, we get a sorted array as our output.

The below image depicts the division array to subarrays of size 1.

In the above example, I have used an array to perform merge-sort. Additionally, we can have LinkedList to perform merge-sort. If we notice, we are dividing our list in the middle. How do we find the middle of the LinkedList?
One of the ways to find mid of the LinkedList is using two pointers. One of the pointers is slow, while the other pointer is fast. The fast one will traverse the LinkedList at twice the speed, hence the name fast pointer.

`def get_middle_linkedlist(self, head):    slow = head    fast = head    while(fast.next and fast.next.next):        slow = slow.next        fast = fast.next.next    return slow`

As we are traversing through the entire list, the time complexity for the above code snippet is O(N). We are not storing any data during the calculation of mid, except for pointers. Hence the space complexity is O(1).

Since we know how to calculate the middle of the LinkedList, let us see the code snippet for dividing the LinkedList.

`def sortList(self, head: ListNode) -> ListNode:    if head == None or head.next == None:       return head    mid = self.get_middle_linkedlist(head)    next_mid = mid.next    mid.next = None    left = self.sortList(head)    right = self.sortList(next_mid)            result = self.sorted_head(left, right)    return result`

We have used recursion to divide the LinkedList. The base condition in our case is when we have no head node or if the node is a single node. Find the mid of the LinkedList using the function get_middle_linkedlist() defined earlier. Keep track of the node next to the middle node. After finding the middle, detach the middle node from its next node, helping in forming separated nodes.

Once we get separated nodes, compare each node’s value with each other, and place them in order. At times, the left/right node can be none, return the other node in those cases.

`def sorted_head(self, left, right):    if left == None:       return right    if right == None:       return left    if(left.val <= right.val):       result = left       result.next = self.sorted_head(left.next, right)    else:       result = right       result.next = self.sorted_head(left, right.next)    return result`

The complete code is as follows.

`class ListSorter:        def sorted_head(self, left, right):        if left == None:            return right        if right == None:            return left        if(left.val <= right.val):            result = left            result.next = self.sorted_head(left.next, right)        else:            result = right            result.next = self.sorted_head(left, right.next)        return result        def get_middle_linkedlist(self, head):        slow = head        fast = head        while(fast.next and fast.next.next):            slow = slow.next            fast = fast.next.next        return slow    #start    def sortList(self, head: ListNode) -> ListNode:        if head == None or head.next == None:            return head        mid = self.get_middle_linkedlist(head)        next_mid = mid.next        mid.next = None        left = self.sortList(head)        right = self.sortList(next_mid)                result = self.sorted_head(left, right)        return result`

Time Complexity

We are dividing our linked list into halves at the divide phase. The time complexity for the divide phase is O(logn) since the division of the LinkedList occurs parallelly. During the merge phase, we go through each node in the LinkedList, which has a time complexity of O(n). Therefore in total, the time complexity is O(nlogn).

Space Complexity

We are using recursion to perform merge-sort and we are traversing through all the nodes. Since recursion uses stack internally, the space complexity is O(n).

I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.

## More from Annamariya Tharayil

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt