Do not miss this exclusive book on Binary Tree Problems. Get it now for free.
Reading time: 15 minutes | Coding time: 20 minutes
Insertion sort is a comparison based sorting algorithm which can be utilized in sorting a Linked List as well. Insertion Sort is preferred for sorting when the data set is almost sorted. The slow random-access performance of a linked list makes some other algorithms such as Quick Sort perform poorly, and others such as Heap Sort completely impossible.
Algorithm
The key idea of Insertion sort is to insert an element into a sorted section of the element set.
A single element is always sorted. Similarly, insertion sort begins with a single element and iteratively takes in consequtive elements one by one and inserts them into the sorted array such that the new element set is sorted as well.
The time complexity of Insertion Sort is O[N^2] and works faster than other algorithms when the data set is almost sorted.
Inserting an element in a sorted Linked List is a simple task which has been explored in this article in depth. Do check it out for better understanding.
Pseudocode
Pseudocode of Insertion Sorting a Linked List:
void insertionSort[] { // Initialize sorted linked list final Node sorted = null; // Traverse the given linked list and insert every // node to sorted Node current = first; while [current != NULL] { // Store next for next iteration Node next = current.next; // insert current in sorted linked list Unlink[current]; // Delete current sortedInsert[current.data]; // Insert current in sorted order // Update current current = next; } }Complexity
- Worst case time complexity: Θ[N ^ 2]
- Average case time complexity: Θ[N ^ 2]
- Best case time complexity: Θ[N]
- Space complexity: Θ[1]
Implementations
Implementation of applying Merge Sort on a Linked List is as follows:
- Java