Insertion sort in doubly linked list

Insertion sort is a sorting algorithm that works by repeatedly taking an element from an unsorted list and inserting it into its proper position in a sorted list. In the context of a doubly linked list, the insertion sort algorithm works by traversing the list from the beginning to the end, comparing each element with the elements that have already been sorted, and inserting the element into the correct position in the sorted sublist.

To perform insertion sort on a doubly linked list, you start by considering the first node as a sorted sublist. Then, you move to the second node and compare it with the first node. If the second node is smaller than the first node, you swap their positions. Otherwise, you leave the second node in its current position.

Next, you move to the third node and compare it with the first two nodes. If the third node is smaller than any of the first two nodes, you insert it in the correct position by rearranging the links of the nodes.

You continue this process for each subsequent node until the entire list is sorted. The advantage of using a doubly linked list for insertion sort is that it allows for efficient insertion and deletion of nodes, making the sorting process faster and more efficient.