So I have tried to make an insertion sort for doubly linked list with iterators. It returns a sorted list with the 'keys' sorted from smaller to bigger. Althought my code doesn't sort the actual list and i am not sure if it's an insertion sort. Can anyone help?

public static List sort(List list) {        
        List sortedList = new List();                  // sortedList
        List.Iter curIndex = List.Iter.last(sortedList);  // terminated forward iterator        
                
        for(List.Iter iter = List.Iter.first(list); !iter.end(); iter.next()) {
            curIndex = List.Iter.last(sortedList);
            List.Node node = iter.key_data();  
            System.out.println("node: " node.data);
            System.out.println("curIndex: " curIndex.key_data().data);
            if (sortedList.empty()) {                
                sortedList.insAfter(curIndex, node.key, node.data);                
            }
            else if (curIndex.key_data().key >= node.key) {
                boolean hasPrev = true;
                while (hasPrev && curIndex.key_data().key >= node.key) {
                    hasPrev = curIndex.prev();                    
                }                                
                sortedList.insAfter(curIndex, node.key, node.data);                        
            }
            else {                            
                boolean hasNext = true;
                while (hasNext && curIndex.key_data().key < node.key) {
                    hasNext = curIndex.next();
                }
                sortedList.insAfter(curIndex, node.key, node.data);                
            }
            
        }
        return sortedList;
    }

CodePudding user response：

Whether or not the definition of insertion sort would still consider your code to be an implementation of that, is probably a matter of interpretation. But in the more strict definition of insertion sort, the algorithm should move nodes, not create new nodes. This is what Wikipedia has as definition:

Insertion sort iterates, consuming one input element each repetition, and grows a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.

I highlight the word removes, which is an action your algorithm does not perform. The same article has a section specifically on linked lists, where it states (my highlights):

If the items are stored in a linked list, then the list can be sorted with O(1) additional space. The algorithm starts with an initially empty (and therefore trivially sorted) list. The input items are taken off the list one at a time, and then inserted in the proper place in the sorted list. When the input list is empty, the sorted list has the desired result.

Your implementation needs O(n) space. It would be more in line with the spirit of insertion sort, if it would do as described in that quote: instead of creating new nodes, it could take the original node object out of the original list, and rewire it so it becomes part of the newly sorted list, such that the whole process does not ever create new nodes.