Time and Space Complexity of Insertion Sort on Linked List

In this article, we have explored Time and Space Complexity analysis of Insertion Sort on Linked List.

Table of Content

1. Overview of Insertion Sort Algorithm on linked list
2. Analysis of Worst Case Time Complexity of Insertion Sort
3. Analysis of Best Case Time Complexity of Insertion Sort
4. Analysis of Average Case Time Complexity of Insertion Sort
5. Analysis of Space Complexity of Insertion Sort
6. Conclusion

Following is the gist of this analysis:

Overview of Insertion Sort Algorithm on linked list

Insertion sort is a comparison based sorting algorithm.

The key idea of Insertion sort on linked list algorithm is to insert an node/element into a sorted linked list.

This method is preferred to use when the elements are almost sorted. Insertion sort begins with a single element and iteratively takes in consecutive elements one by one and inserts them into the sorted list on its place without disturbing the sorted order.

Learn with an example

Input list:
[5]->[-1]->[0]->[4]->[2]

Output:
[-1]->[0]->[2]->[4]->[5]

Take a new list(let name of new list be S) which will our sorted list and the given input unsorted list.

Input list:
[5]->[-1]->[0]->[4]->[2]

S:

Now, lets start doing the comparisions, if the S list is empty then insert the first node of Input list into S

Input list:
[-1]->[0]->[4]->[2]

S:
[5]

Now, compare the first node value of 'Input list' with the node values in 'S' and place the value in S according to sorted order. Like,

Input list:
[0]->[4]->[2]

S:
[-1]->[5]

Similarly, after some iterations, Input list will be empty and S will have all elements of initial Input list.

Therefore, lists will look like,

Input list:

S:
[-1]->[0]->[2]->[4]->[5]

The Code of Insertion Sort on Linked List is as follows:

//Insertion Sort
   begin insertion_sort ( root_node )   //root_node is pointing at input list
       S = NULL    //initializing sorted linked list and assigning Null
       while ( root_node )
       {
       x = root_node->next   //intializing x new node and assigning root-node's next node in it
       temp = S    //initializing temp new node and assigning it S
       
       while ( temp->next && temp->next->value < root_node->value)   //checking conditions
       { 
       temp = temp->next   //updating temp to temp's next
       }
       root_node->next = temp->next
       temp->next = root_node
       root_node = x
       }
       return S
   end insertion_sort

Here, we are appling the idea of putting the element from input list to new sorted node 'S', using comparision of elements and shifting of elements.

Time Complexity Analysis of Insertion Sort on linked list

After each pass, the size of sorted list 'S' increases by 1 and size of unsorted input list decreases by 1. Hence, for a few steps are as follows:

Pass 1: number of comparision: 1, number of Shift: 1
Pass 2: number of comparision: 2, number of Shift: 2
Pass 3: number of comparision: 3, number of Shift: 3
and so on till
Pass n: number of comparision: n, number of Shift: n.

Hence, Total number of comparisions: (n*(n-1))/2
and Total number of shifts: (n*(n-1))/2

Time Complexity of function is depending on Number of comparisions + shifts.

Hence, the time complexity of insertion sort on linked list is O(n^2).

Analysis of Worst Case Time Complexity of Insertion Sort

The worst case is the case when,

Suppose we need to arrange list in ascending order and given the input list is decreasing order then there will be maximum number of shiftings in sorted list 'S' for every element. For example, if the input list is 8, 6, 5, 4, 2, then,

Pass 1: number of comparision: 1, number of Shift: 1,
S: 8, input_list: 6, 5, 4, 2
Pass 2: number of comparision: 2, number of Shift: 2,
S: 8, 6, input_list: 5, 4, 2
and so on till
Pass 5: number of comparision: 5, number of Shift: 5,
S: 8, 6, 5, 4, 2, input_list:

Hence, Number of comparision: n*(n-1)/2 , number of Shift: n*(n-1)/2.
Therefore, Worst case time complexity is O(n^2).

Analysis of Best Case Time Complexity of Insertion Sort

The best case is a case when,

Suppose we need to find the ascending order and given input list is also in ascending order then there will be 0(zero) shifting in 'S'. For example, if the input list: 2, 4, 6, 8, 10, then,

Pass 1: number of comparision: 1, number of Shift: 0,
S: 2, input_list: 4, 6, 8, 10
Pass 2: number of comparision: 1, number of Shift: 0,
S: 2, 4, input_list: 6, 8, 10
and so on till
Pass 5: number of comparision: 1, number of Shift: 0,
S: 2, 4, 6, 8, 10, input_list:

Hence, there is zero shiftings and total n comparisions.
Therefore, Best case time complexity is O(n).

Analysis of Average Case Time Complexity of Insertion Sort

Based on the worst case and best case, the average number of comparisions for every element will be half of worst case and similarly with the average number of shifting will be half of worst case.Like

Pass 1: number of comparision: 1, number of Shift: 1,
Pass 2: number of comparision: 2/2, number of Shift: 2/2,
Pass 3: number of comparision: 3/2, number of Shift: 3/2,
and so on till
Pass n: number of comparision: n/2, number of Shift: n/2,

Hence, there is n*(n-1)/4 comparisions and shiftings.
Therefore, average case time complexity is O(n^2).

Analysis of Space Complexity of Insertion Sort

The space complexity of Insertion Sort on linked list is constant, this is because we use only constant extra spaces for 2 lists and for some new nodes in function to perform comparisions and shifting of nodes.

Hnece, the space complexity of Insertion sort on linked list is O(1).

Conclusion

Long story short,

• Worst Case Time Complexity of insertion sort on linked list is O(n^2).
• Average Case Time Complexity of insertion sort on linked list is O(n^2).
• Best Case Time Complexity of insertion sort on linked list is O(n).
• Space Complexity of insertion sort on linked list O(1).

With this article at OpenGenus, you must have a strong idea of Time and Space Complexity of Insertion Sort on Linked List.