Sort A “K” Sorted Doubly Linked List

We will use Insertion sort to sort the doubly linked list efficiently. 

Iterate the given doubly linked list head till the last node n, where n is the size of the doubly linked list.

• Compare the current element (key) to its predecessor.
• If the key element is smaller than its predecessor, compare elements before. Move the greater elements one position up to make space for the swapped element.

Let’s understand this in a detailed way.

• Start by making a Node *current = head and then run a loop till current is not NULL.
• Make a Node *back = current -> prev and an integer variable named key = current->data.
• Now run a loop till back is not NULL and the key is less than current->data.
• Inside this loop update back -> next -> data = back -> data and back= back -> prev.
• After exiting this loop check if the back is NULL or not. If it is NULL, then update head -> data = key;
• Else update back -> next -> data = key, and after this update current = current -> next.
• At last return head, which is our answer.

• We will start by creating a Min Heap(or a priority queue) of size k+1 with the data of the first k+1 nodes. Also make two pointers named next and prev, where prev points to the previous node and next point to the next node.
• We will maintain a priority queue giving priority to the minimum element(min-heap) and we’ll then insert the data of the first k+1 nodes in the queue.
• We will run a loop from k+1 till N(Number of nodes in the doubly linked list). We will then start assigning the top element of the queue to the data of the first node of the doubly linked list(we’ll initialize a variable index=0) and then pop this value and also increment the index.
• At the same time, we will push the value at which the next pointer is pointing in the loop(it can be from K+1 to N).
• After this loop terminates, i.e all the elements from the doubly linked list have been added to the queue. Then, we will just assign the top element of the queue to the linked list and pop that value. We will do this till the queue is empty.
• Finally, we will print the K sorted doubly linked list.

Let us understand the working of the above algorithm with the help of an example, where N(Number of nodes in the doubly linked list) = 4, K = 2, and the doubly linked list is:

                     NULL←5←→6←→2←→3→NULL

• We will create a priority queue of size 3(K + 1) and insert the first 3 values {5, 6, 2} in it and also create an integer variable index which is initialized to be 0.
• Then we will run a for loop from 3(K + 1) to 4(N) and start assigning the linked list(from the start of the linked list using index variable which was initialized to be 0), to have the value of the top of the queue which will return the value of the smallest value from the queue which will be 2. Hence our first element in the answer linked list is 2, now we will pop this out of the queue and push a new element in the linked list which will be 3.
• Now in our case, our loop is terminated as N = 4(Number of nodes in the doubly linked list) has been achieved, so we need not push more elements in the list.
• We’ll keep assigning the top element of the queue to our final list, and pop the top element till the queue becomes empty, and finally print the final linked list.
• After we pushed 3 in our queue, our 2nd element of our final linked list which is nothing but the top of the queue will be added to the final linked list and our new linked list will look like {2, 3}.
• Similarly, we’ll add 5 and 6 to our final linked list and pop them from the queue, and finally now as the queue is empty we’ll just print our final linked list which is {2, 3, 5, 6}.