Timeline for In-Place Reordering of Doubly Linked List Nodes to Ensure Memory Contiguity
Current License: CC BY-SA 4.0
4 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Jul 4 at 4:58 | comment | added | gnasher729 | There’s the minor problem here that the sort key (the address of the node) changes throughout the sorting process. | |
Jul 3 at 21:37 | comment | added | Mark | An in-place sort is inefficient: you already know where each node belongs, so you can reorder in O(n) time, with just a single pass through the list. | |
Jul 3 at 19:44 | comment | added | JounceCracklePop | Perhaps it's an under-specified question, but my interpretation is that the next pointer is to another position in the array. So every swap will involve changing the values you're sorting by, or breaking the links. This is not a complete solution. | |
Jul 3 at 8:24 | history | answered | codeR | CC BY-SA 4.0 |