I don't think this is what hayley-patton meant (although it's not crystal clear). I think SBCL does memory management with a bump allocator and a moving collector. So if you build a linked list sequentially, the cons cells will be allocated sequentially, and will be sequential in memory. If you build it in random order, they won't be. But when the collector runs, it will move the whole list, and it will move the cells in sequential order, and then it will be.
That implies you took the time to sort them, so your O(1) insertion time just became O(N log N). Sure, that cost is spread over how ever many inserts you did between GCs but it isn't O(1) anymore.
SBCL cheats and copies starting from the first cons cell that is referenced from outside the list; this tends to be the start of the list, and so traversing just works. The contiguous copying also ends when a cons cell which was already copied is found, so there can't be more discontinuities than there are cons cells referenced from outside the list, regardless of which order we discover the references.