Insertion Sort Linked List

Difficulty: Medium, Asked-In: Microsoft, Google

Key takeaway: An excellent problem to iterative problem solving in a linked list.

Let’s understand the problem

We have given the head of a singly linked list, write a program to sort the list using insertion sort, and return the head of the sorted linked list.

Suppose all elements in the linked list are unique.
Value can be positive, negative, or zero.

Examples

Input: [6] -> [2] -> [7] -> [4] ->NULL
Output: [2] -> [4] -> [6] -> [7] ->NULL

Input: [3] -> [-4] -> [-3] -> [1] -> [0] -> NULL
Output: [-4] -> [-3] -> [0] -> [1] -> [3] -> NULL

A short Introduction to Insertion sort on an array

To understand the implementation, we need to revise the idea of insertion sort on array.

Insertion sort adds one input to the sorted output at each step of iteration and grows partially sorted array size by 1. In other words: At each iteration, insertion sort removes one element from the input data and finds its location in the partially sorted array. This process repeats until no input elements remain.

At any ith iteration of the insertion sort, it divides the array into three parts: current element(A[i]), partially sorted part(A[0…i — 1]), and unsorted part (A[i+1…n-1]). So at each iteration, insertion sort picks the first element from the unsorted part, find position of that element within the sorted part, and insert it there.

Implementation of Insertion sort on linked list

We can use the same idea to implement a linked list insertion sort. But there are some key differences:

Linked list insertion sort visualization

Solution idea

We start from the unsorted linked list and run a loop to pick each node. To insert the current node in sorted output, we can use a helper function sortedInsert().

This function accepts the head of the partially sorted list and a current node as an argument. Inside the function, we iterates through the start of the list until it finds an element greater than current node. Finally, it return the head of partially sorted linked list.

At each iteration of above loop, we add one node to the correct position in the partially sorted list. In other words, partially sorted list size will grow by 1 at each iteration.

Solution steps

Initialize a pointer curr to track the current element i.e. curr = head.
Initialize a pointer sortedHead to track the head of sorted list i.e. sortedHead = NULL
Traverse the linked till curr != NULL.
Before inserting curr node at the correct position in partially sorted list, we mark the next node using another pointer currNext, i.e currNext = curr->next.
Now we insert curr node in the partially sorted part using the helper function i.e. sortedHead = sortedInsert(sortedHead, curr).
We move curr pointer to the next node i.e. curr = currNext.
By the end of loop, return the head of sorted linked list as an output.

Solution pseudocode

ListNode insertionSortLinkedList(ListNode head)
{
    ListNode curr = head
    ListNode sortedHead = NULL
    while (curr != NULL)
    {
        ListNode currNext = curr->next
        sortedHead = sortedInsert(sortedHead, curr)
        curr = currNext
    }
    return sortedHead
}

Implementation of helper function sortedInsert(sortedHead, curr)

All the nodes before curr node are sorted and our goal is to insert curr node in the partially sorted list. So we start from the head and compare each node data with data stored in curr node.

When this function get called for the first node (sortedHead == NULL) or head data is greater than curr node data (sortedHead->data >= curr->data), we insert curr node to the front and return curr pointer as an output.
```
if(sortedHead == NULL || sortedHead->data >= curr->data)
{
  curr->next = sortedHead
  return curr
}
```

Otherwise, we run a loop to skip all the nodes less than curr->data.

ListNode temp = sortedHead
while(temp->next != NULL && temp->next->data < curr->data)
   temp = temp->next

By the end of above loop, temp pointer is at the node which is just less than the curr->data. In the worst case, temp may reach to the last node. Whatever be the situation, we need to insert curr node to the next of temp.
```
curr->next = temp->next
temp->next = curr
```
Finally, we return sortedHead as an output.

Pseudocode implementation of sortedInsert()

ListNode sortedInsert(ListNode sortedHead, ListNode curr)
{
    // Insertion at the first position
    if(sortedHead == NULL || sortedHead->data >= curr->data)
    {
        curr->next = sortedHead
        return curr
    }
    else
    {
        ListNode temp = sortedHead
        while(temp->next != NULL && temp->next->data < curr->data)
            temp = temp->next
        curr->next = temp->next
        temp->next = curr
    }
    return sortedHead
}

Analysis of insertion sort on linked list

In the worst case, we need to traverse complete partially sorted list to insert a node at the correct position. Suppose i number of nodes are sorted and we want to insert (i+1)th node using the helper function. Then total number of comparison operation in the worst case = i. This is a situation of already sorted linked list.

Total count of comparison operation in the worst case = 1 + 2 + 3 + ... + n - 1 = n(n-1)/2 = O(n^2)

The best case situation occur when linked list is reverse sorted, where we need to perform one comparison operation and insert every node at the front of the linked list.

Total count of comparison operation in the best case = 1 + 1 + 1 + ... n times = n = O(n)

As we are using constant number of pointers, space complexity = O(1)

Critical ideas to think about!

Which is the fastest algorithm for sorting a linked list: Insertion sort, merge sort, or quicksort? Implement and compare time complexities.
What is the average case complexity of the above algorithm?
Can we think of optimizing the above code further?
Can we think of implementing the above algorithm recursively?
Can we think of implementing the above code if we initialize sortedHead with the head node, curr node with head->next and run a while loop till curr != NULL? What would be different boundary conditions?
Insertion sort on array works in O(n) for a partially sorted array with O(n) number of inversions. Does such a benefit exist in the case of a linked list?

Another implementation without using helper function

ListNode insertionSortList(ListNode head) 
{
    if (head == NULL)
		return head
		
	ListNode dummy = new ListNode(0)
	ListNode currNode = head
	ListNode prevNode = dummy
	ListNode nextNode = NULL
	while (currNode != NULL)
	{
		nextNode = currNode->next
		while (prevNode->next != NULL && prevNode->next->data < currNode->data)
		    prevNode = prevNode->next
		
		currNode->next = prevNode->next
		prevNode->next = currNode
		prevNode = dummy
		currNode = nextNode
	}
	return dummy->next
}

Sort Linked List using Insertion Sort Algorithm