Sorting a linked list using insertion sort

In one of my previous posts, we have seen how a linked list can be sorted using bubble sort approach. In this post we will see how we can sort a linked list using insertion sort algorithm. Like bubble sort this approach will also take O(n2) time.

Here is the strategy for linked list insertion sort. We maintain two lists; one sorted and another unsorted. Initially the sorted list is empty and the unsorted list will be the original list. In each iteration, we remove a node from the unsorted list and add it the sorted list in proper position. I re-used the procedure for inserting data into a sorted linked list from this post.

The following diagram should give you some understanding of the procedure.

Here is the C++ implementation of the above algorithm.

Inserting an element into sorted linked list

Given a sorted linked list write a program to insert data into it’s correct position.
For example consider the following linked list

1 -> 3 -> 4 -> 5

Inserting 2 should change the list to

1 -> 2 -> 3 -> 4 -> 5
Inserting 0 should change it to
0 -> 1 -> 2 -> 3 -> 4 ->5
Inserting 6 should change it to
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6.
The three examples indicate three different cases to be considered while inserting into a sorted linked list.
Case 1: List can be empty or new element is added as the first element
Case 2: New element can be inserted anywhere in the middle of the linked list
Case 3: New element is added as the last element.

The following diagram illustrates the insert process.

In the following C++ program case 1 is handled in one block and case 2 and 3 are handled in the last block.