## Sort a linked list using insertion sort Difficulty: Medium

#### Understanding the Problem

Problem Description: Sort a linked list using insertion sort and return its head.

``````Example 1
Input: 8->0->1->3
Output: 0->1->3->8

Example 2
Input: -1->7->3->4->2
Output: -1->2->3->4->7``````

Possible follow-up questions to ask the interviewer :

• Are there any repeating elements in the linked list? (Ans: Yes)

The node structure for the Linked List passed to your function will be

``````class Node
{
int val
Node next
Node(int v)
{
val = v
next = NULL
}
}``````

#### Solution Approach

Let us first understand the flow of insertion sort. At any point of time in insertion sort, it divide the array into three parts

1. Current element
2. Sorted part
3. Unsorted part

Everything before the current element is sorted part and everything after the current element is unsorted part.At each iteration we will pick the first element from the unsorted part, we will find the position of that element within the sorted list, and insert it there. It repeats until no element is present in the unsorted part.

To insert, we will use a helper function sortedInsert() which will return the head of the sorted list after insertion. sortedInsert() accepts a list head and a node as an argument and iterates through the list until it finds an element greater than the node.

Solution Steps
1. Initialize curr = head, curr will store the current element.
2. Create and initialize a node sorted_head to track the head of the sorted list. Initialize it i.e. sorted_head = NULL
3. Iterate the list until curr != NULL
• Store the next element after the curr in a node, i.e currNext = curr.next.
• Insert the curr in the partially sorted part using the sortedInsert function and update head of the sorted list, i.e sorted_head = sortedInsert(sorted_head, curr).
• Set curr = currNext.

Pseudo Code
``````Node insertionSortLinkedList(Node head)
{
while (curr != NULL)
{
Node currNext = curr.next
curr = currNext
}
}``````
``````Node sortedInsert(Node sorted_head, Node new_node)
{
// Insertion at first position
{
return new_node
}
else
{
while(curr.next != NULL and
curr.next.data < new_node.data)
curr = curr.next
new_node.next = curr.next
curr.next = new_node
}
}``````
Complexity Analysis

In the worst case, we could have to traverse the whole partially sorted list to insert a node in the correct position.(Think!)

Time Complexity: (Traversing the list) * (Inserting in Sorted List)

= O(n)*O(n) = O(n²)

Space Complexity = O(1)

Critical ideas to think!
• Which is the fastest algorithm for sorting a linked list: Insertion Sort, Merge sort or Quicksort? Implement and Compare the time & space complexities.
• What is the best case complexity of the above algorithm? Also, try to find the condition when it achieves its best case?

#### Suggested problems to solve

• Merge Two Sorted Lists
• Merge Sort in an array.
• Merge sort in the linked list.