How the insertion sort works

Besides explaining the particular code implementation, I would briefly describe the mechanism of insertion sort and provide an illustrated visual for the sorting process. Generally, the basic working mechanism of insertion sort is that it picks the first element to assume it is located on the sorted side, in the code implementation I pick the head pointer and assigned it to the picked node pointer. To perform comparing between node and swap, the insertion sort mechanism will need to pick the key in this list and in code implementation, this key is the currentNode. The program will perform compare the first node and the key node. For instance, I have a doubly linked list as below: Because this operation sorts ascendingly, if the pickedNode is greater than currentNode, the program swaps them: However, it’s only in terms of illustration. In real code implementation, instead of providing more if-else statements or redundancy of unnecessary code, the condition is combined in a while loop. Because after each loop, the picked Loop is set to the next node until it reaches the tail, the outside while needs to come with the condition that it will run until the picked Node is null. And because when the picked Node is not null, the current node is assigned to the next node of the picked node according to the mechanism of insertion sort. The condition in the nested while is quite abstracted; hence, I describe it via the illustrated visual below: Assuming now the picked node is the third node and the current node is after the picked node Now because the current node is not null and the previous node of it also, the program performs comparing these two. At the first glance, we can also see that 11 is less than 33; so, the condition now is met(condition: current node and the previous node are not null, the previous node data of a current node is less than the current node). It comes to the code inside the nested while, the program will call swap operation to swap these two(just swap the data of node without swapping their next and previous pointer). Because the mechanism of insertion sort is it will pick the current node and compare it with all the elements of the sorted side(the side with the last element is the picked node). To follow that in code implementation, the current node will be back to the previous node and the process will be iterated until it doesn’t meet the condition of these two while loops. To illustrate, I continue the above process: Swap data of nodes in comparing above. Continue back the current node to the previous node and compare. This process will continue until there are no previous nodes of the current node(the previous node is null now). Now looking at the position of the initial current node(after the picked node), from this to any previous element is the sorted linked list. Thereby, the currentNode will be set to the fourth node and the program continue the while loop until the linked list is absolutely sorted.