Best sorting algorithm - Partially sorted linked list

Question

Problem- Given a sorted doubly link list and two numbers C and K. You need to decrease the info of node with data K by C and insert the new node formed at its correct position such that the list remains sorted.

I would think of insertion sort for such problem, because, insertion sort at any instance looks like, shown bunch of cards,

that are partially sorted. For insertion sort, number of swaps is equivalent to number of inversions. Number of compares is equivalent to number of exchanges + (N-1).

So, in the given problem(above), if node with data K is decreased by C, then the sorted linked list became partially sorted. Insertion sort is the best fit.

Another point is, amidst selection of sorting algorithm, if sorting logic applied for array representation of data holds best fit, then same sorting logic should holds best fit for linked list representation of same data.

For this problem, Is my thought process correct in choosing insertion sort?

Answer 1

Maybe you mean something else, but insertion sort is not the best algorithm, because you actually don't need to sort anything. If there is only one element with value K then it doesn't make a big difference, but otherwise it does.

So I would suggest the following algorithm O(n), ignoring edge cases for simplicity:

1. Go forward in the list until the value of the current node is > K - C.
2. Save this node, all the reduced nodes will be inserted before this one.
3. Continue to go forward while the value of the current node is < K
4. While the value of the current node is K, remove node, set value to K - C and insert it before the saved node. This could be optimized further, so that you only do one remove and insert operation of the whole sublist of nodes which had value K.

Answer 2

If these decrease operations can be batched up before the sorted list must be available, then you can simply remove all the decremented nodes from the list. Then, sort them, and perform a two-way merge into the list.

If the list must be maintained in order after each node decrement, then there is little choice but to remove the decremented node and re-insert in order.

Doing this with a linear search for a deck of cards is probably acceptable, unless you're running some monstrous Monte Carlo simulation involving cards, that runs for hours or day, so that optimization counts.

Otherwise the way we would deal with the need to maintain order would be to use an ordered sequence data structure: balanced binary tree (red-black, splay) or a skip list. Take the node out of the structure, adjust value, re-insert: O(log N).