Why is merge sort the natural sort for a linked list but quicksort is not?

## Start from the access model, not the algorithm A linked chain supports two things cheaply: look at the current node, and step to the next one. Everything else is a walk. Reaching position i costs O(i), and there is no way to jump from one position to an arbitrary other. Contrast an array, where any index is O(1) and neighboring elements sit next to each other in memory. Every sorting algorithm is a pattern of accesses. Ask which patterns the structure can serve cheaply, and the choice of sort answers itself. ## Why merge sort fits Merge sort's access pattern is: split the input, sort the pieces, combine two sorted runs by walking both from the front. That combine step reads each run strictly forward and never needs to look backwards or jump. On arrays the combine is where the cost lives: you cannot write the merged run over the inputs without destroying unread values, so the classic implementation allocates a buffer of size n — the reason merge sort is described as the O(n)-extra-space sort. On a list that cost evaporates. The merged run is built by rewriting link fields on nodes that already exist: one comparison per output node, one link write, and a single splice when one run is exhausted. No buffer, no copying of payloads. What is left is the recursion and the split. Top-down, each level walks the chain to find its boundary and the recursion holds O(log n) frames of stack. Bottom-up — merge adjacent runs of length 1, then 2, then 4, iteratively — removes even that, giving O(n log n) worst-case time in O(1) auxiliary space. There is no comparison sort with a better worst-case time bound, so on a list you get the optimal guarantee at essentially no space cost. It also happens to preserve the relative order of equal keys when the merge breaks ties toward the earlier run, which matters when the events being sorted carry a meaningful arrival order. ## Why heapsort does not fit Heapsort's efficiency comes from storing a complete binary tree implicitly in an array: the children of position i live at 2i+1 and 2i+2, so sift-down walks the tree by arithmetic alone, each hop O(1) and in-place. A list has no positions to compute with. Each hop would become a traversal from the head, and the algorithm's cost collapses. You can of course build an explicitly linked heap, but then you are maintaining child references and a notion of the last position by hand, and you have abandoned the property — in-place array manipulation — that made heapsort attractive in the first place. The realistic option is to copy into an array and heapsort there, which is a different decision. ## Why quicksort merely *can* fit The common claim that quicksort is impossible on a list is too strong, and an interviewer will probe it. Partitioning by relinking is straightforward: walk the chain once, splice each node onto a "less" chain or a "not less" chain, then recurse and concatenate. That is O(n) per level with O(1) extra space and no random access at all. The problem is that nothing survives except the recurrence. - **Pivot quality.** Quicksort's practical safety comes from choosing pivots cheaply from sampled positions. Sampling positions costs traversals here, so implementations settle for the head, which is exactly the choice that turns already-sorted input — the common case in an append-ordered event log — into the O(n^2) worst case. - **Locality.** Array quicksort's real advantage is a tight scan-and-swap over contiguous memory that hardware prefetches beautifully. Relinking nodes scattered across memory gives none of that. - **Guarantees.** The worst case stays quadratic no matter how the partition is implemented, whereas merge sort's O(n log n) is unconditional. So you would be choosing a harder implementation, a worse guarantee, and no speed advantage. That is the honest comparison to give: not "it cannot be done", but "it can, and every reason to want it is gone". ## The senior caveat Asymptotics are not the whole answer, and pretending otherwise is its own red flag. Every step of a list merge follows a reference that may live anywhere in memory; the cache misses can cost far more than the comparisons. For a large batch sort, gathering the elements into contiguous storage, sorting them there with whatever the platform's tuned sort is, and rebuilding the chain is frequently faster in wall-clock terms — at the price of O(n) space and of invalidating nothing except your pride. Choose the in-list merge sort when the data must *stay* linked: nodes are shared with other structures, external references to individual nodes must remain valid, or elements are constantly spliced in and out and copying would dominate. Name that condition when you defend the choice, and the answer stops being a recital and becomes a judgment.